/* Recurse.cpp */
/*  Test file for Stack Free Recursion Article */
/*  (C)opyright 1995, Otto J. A. Smith         */

/*  Main() is at end of file                                 */

/*  Put your necessary system includes here */
#include    <os2.h>
#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>
#include    <iostream.h>
/* The routine main() uses the C++ "<<" operator */
/* If you are in true C you need to replace these with printf's */

/*  The Following variables are used as globals in stack free calls */

int x;
int Number_of_Disks;    
char * fromTower,  * toTower, * otherTower;
unsigned long stack;       //These are all global values
unsigned long a, b, c, d;


/******** RECURSIVE FACTORIAL                                   *******/
int factorial(int x)
{
  int prod;
  if(x <= 0) prod = 1;
  else prod = x * factorial( x-1 );
  return prod;
}
/****************************                                   *******/
/******* STACKLESS FACTORIAL                                    *******/
                                        /* Set x to the value you wish to find the factorial of */
int fact2()                             /* Pass x as Global No data Stack */
{
  int prod;
  x = x-1;                              /* A function */
  if(x+1<=0) prod = 1;
  else prod = (x+1) * fact2();      /* The recursive call */
  x = x+1;                              /* A function inverse */
return prod;
}   

/*******************************                                *******/
/******* TOTALLY STACKLESS FACTORIAL                            *******/
int fact3(int x)                        /* This entry point is used only once.  It is not a recursive entry. */
{                                       /* Note that within this routine we treat x as a global. */
  int prod;                             /* Same as in routine above */
  int ox = x;                           /* Original x */

  recursive_entry:                      /* A label we will return to */
     x = x-1;                           /* A function as above */

     if( x<=0 ){ prod = 1; }
     else { goto recursive_entry;  return_entry:  prod = (x+1) * prod;  }

     x = x+1;                           /* Inverse */
     if( x != ox ) goto return_entry;
 
    return prod;
}
/**********************************                             *******/
/******* MODIFIED TOTALLY STACKLESS                             *******/
int fact4(int x)
{
  int prod;
  int ox = x;
  recursive_entry:
     x = x--;
     if( x<=0 ){ prod = 1; x++; }
     else { goto recursive_entry;  return_entry:  prod = (x++) * prod;  }
     if( x != ox ) goto return_entry;
     return prod;
}
/*************************************                          *******/
/******* TOWERS OF HANOI                                        *******/
void Hanoi(int Number_of_Disks, char * fromTower, char * toTower, char * otherTower)
{
   if( Number_of_Disks > 0 )
   {
     Hanoi( Number_of_Disks-1, fromTower, otherTower, toTower);
     cout << " MOVE 1 disk from " << fromTower << " TO " << toTower;
     Hanoi( Number_of_Disks-1, otherTower, toTower, fromTower);
   }
}
/******************************/
/******* PARTIALLY STACKLESS TOWERS OF HANOI *******/
                                /* int Number_of_Disks;    //Now a global value!! */
void Hanoi2(char * fromTower, char * toTower, char * otherTower)
{
   if( Number_of_Disks > 0 )
   {
     Number_of_Disks = Number_of_Disks-1;
     Hanoi2(fromTower, otherTower, toTower);
     cout << " MOVE 1 disk from " << fromTower << " TO " << toTower;
     Hanoi2(otherTower, toTower, fromTower);
     Number_of_Disks = Number_of_Disks+1;
   }
}
/**************************************/
/******* STACKLESS TOWERS OF HANOI *******/
                                /* int Number_of_Disks;    //Now a global value!! */
                                /* char * fromTower,  toTower,  otherTower; */
void Hanoi3()
{
   char * TEMP;
   if( Number_of_Disks > 0 )
   {
     Number_of_Disks = Number_of_Disks-1;
         TEMP = otherTower;        //These three lines are there own inverse
         otherTower = toTower;
         toTower = TEMP;
     Hanoi3();
         TEMP = otherTower;        //See above
         otherTower = toTower;
         toTower = TEMP;
     cout << " MOVE 1 disk from " << fromTower << " TO " << toTower;
         TEMP = otherTower;
         otherTower = fromTower;
         fromTower = TEMP;
     Hanoi3();
         TEMP = otherTower;
         otherTower = fromTower;
         fromTower = TEMP;
     Number_of_Disks = Number_of_Disks+1;
   }
}
/***********************************/
/******* RECURSIVE LINE DRAW *******/
/****  You must write your own routine to place a real line ****/
void color(int a, int b)
{
  cout << " Color cell (" << a << "," << b << ") \n";
}

void Line_Draw(int a, int b, int c, int d)
{
  if( (a==c ) && ( b==d ) )
  {
    color(a,b);
  }
  else
  {
   Line_Draw(a,            b,            a+c>>1, b+d>>1);
   Line_Draw(a+c+1>>1, b+d+1>>1, c,         d        );
  }
  return;
}
/*********************************/
/******* STACKLESS (SORT OF) RECURSIVE LINE DRAW *******/
                                /* unsigned long stack;       //These are all global values */
                                /* int a, b, c, d; */
                                /* Set initial values of a, b, c, d here. */
unsigned long SR(unsigned long X)
{
  stack = stack << 1;
  if( X & 1 ) stack = stack + 1;
  return X >> 1; 
}

unsigned long SL(unsigned long X)
{
  X = X << 1;
  if( stack & 1 ) X=X+1;
  stack = stack >> 1;
  return X;
}

void Line_Draw2()
{
  if( (a==c ) && ( b==d ) )
  {
    color(a,b);
  }
  else
  {
   d = SR(b+d);
   c = SR(a+c);
     Line_Draw2();
   c = SL(c) - a;
   d = SL(d) - b;

   b = SR(b+d+1);
   a = SR(a+c+1);
     Line_Draw2();
   a = SL(a)-c-1;
   b = SL(b)-d-1;
  }
  return;
}

/******************************/
/********************** MAIN *************************************/

void main()
{
cout << " 5! calculated using standard recursion = ";
cout << factorial(5) << '\n';
cout << " 5! calculated using data stack free recursion = ";
x = 5;
cout << fact2() << '\n';
cout << " 5! calculated with completely stack free recursion = ";
cout << fact3(5) << 'n';
cout << " Do Towers of Hanoi using standard recursion. \n";
Hanoi(4,"Tower1","Tower2","Tower3");
cout << '\n';
cout << " Do Towers of Hanoi using intermediate recursion. \n";
Number_of_Disks = 4;
Hanoi2("Tower1","Tower2","Tower3");
cout << '\n';
cout << " Do Towers of Hanoi using data stack free recursion. \n";
Number_of_Disks = 4;
fromTower = "Tower1";
toTower = "Tower2";
otherTower = "Tower3";
Hanoi3();
cout << '\n';
cout << " Do line draw using standard recursion. \n";
Line_Draw(0,0,3,5);
cout << '\n';
cout << " Do line draw using data stack free recursion. \n";
a=0;
b=0;
c=3;
d=5;
Line_Draw2();
cout << '\n';
cout << "End of file \n";
cout << '\n';
return;
}