dexter4life Posted March 3, 2012 Posted March 3, 2012 Writing a program that recurses depends heavily on the stack; Is this a true fact? Example of a program is the legendary Towers of hanoi. //------------ //dexter #include<iostream> //the c++ standard library for stream input output #include<cstdio> //the c standard library for standard input output #include<cstdlib> //for the exit function using namespace std; class arr //arr class that holds each stag { public: int a[100],b[100],c[100]; int topa,topb,topc; }hanoi; int move=1; //counts the no. of moves int main() { void tower(int ,int *,int *,int *,int *,int *,int *); //function prototype void show(int); //function prototype int i; system("clear"); cout<<"Enter the no of elements for which u want to solve the problem "; scanf("%d",&i); system("clear"); for(int j=0;j<i;j++) //feeds the elements in the arrs; { hanoi.a[j]=j+1; hanoi.b[j]=-1; hanoi.c[j]=-1; } hanoi.topa=i-1; //topa,topb,topc,mean the top of each arr hanoi.topb=-1; hanoi.topc=-1; cout<<" Initially "<<" "; for(int j=i-1;j>-1;j--) //show the statusm of each arr { show(hanoi.a[j]); show(hanoi.b[j]); show(hanoi.c[j]); cout<<" "; } cout<<" "; tower(i,hanoi.a,hanoi.c,hanoi.b,&(hanoi.topa),&(hanoi.topc),&(hanoi.topb)) ; //call to do the job } void tower(int n,int src[],int dest[],int aux[],int *ts,int *td,int *ta) //the tower function passes { //the arrs along with the top pointers void show (int); if(n==1) //if one element is there in source arr , { //then it is moved to the destination arr, dest[++(*td)]=src[(*ts)]; src[*ts]=-1; (*ts)--; int max; max=((*ts)>(*td)?(*ts)*td)); max=(max>(*ta)?max:(*ta)); cout<<" Move "<<move++<<" "; for(int i=max;i>-1;i--) //status of arrs shown { show(hanoi.a); show(hanoi.b); show(hanoi.c); cout<<" "; } cout<<" "; return; } tower(n-1,src,aux,dest,ts,ta,td); //else the tower(1,src,dest,aux,ts,td,ta); // problem is solved by tower(n-1,aux,dest,src,ta,td,ts); // recursive calls } void show(int a) //the show function shows the current status of the arrs { if(a==-1) cout<<"- "; else cout<<a<<" "; }
deepzero Posted March 3, 2012 Posted March 3, 2012 true fact? facts are always true, but yes, they do. Think about it: every time you call your function (lets call it x), the local variables are reserved on the stack; when you exit the function, they are "freed" again. If you now call x from within x, the call happens BEFORE the space for the local variables is given back to the stack, and thus you need space on the stack for two sets of local variables used in your function x. This increases linear. besides that: -use tags (i did not read your code) -be aware of over commenting d.
metr0 Posted March 3, 2012 Posted March 3, 2012 Mind that recursion not always implies heavy stack usage, as the compiler might optimize the code well enough to make it use no (additional) stack space at all. See tail recursion, which is a heavily employed idiom in function languages.
dexter4life Posted April 2, 2012 Author Posted April 2, 2012 I Understand. The problem that i have about recursion is understanding how every instance of the function that is call make use of the stack.Like this program:#include <iostream>#include <iomanip>using namespace std; TowersOfHanoi(int , int , int , int ); //function prototypeint main( int argc, char *argv[] ){ TowersOfHanoi(3,1,3,2); ///non-recursive callreturn 0;}void TowersOfHanoi(int disks, int sourcePeg, int destinationPeg, int tempPeg ){if( disks == 1 ){cout << sourcePeg << " --> " << destinationPeg << endl;return;}TowersOfHanoi( disks - 1, sourcePeg, tempPeg, destinationPeg );//recursive callcout << sourcePeg << " --> " << destinationPeg << endl;TowersOfHanoi(disks-1,tempPeg,destinationPeg, sourcePeg );//recursive call}////endPlease some body explain to me how this program use the stack to implement it functions.
deepzero Posted April 2, 2012 Posted April 2, 2012 when you call a function, space for the local variables is reserved on the stack.When you return (ie hit a return statement) from your function, this space is "given back" to the stack.If you now call TowersOfHanoi from within TowersOfHanoi, you do not hit a "return", and the space reserved for the local variables is still reserved. Plus, since you just called TowersOfHanoi again, stack-space for the local variables needs to be allocated.please use code tags in the future...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now