/* 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 #include #include #include #include /* 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; }