Recursion

[dexter4life]

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]

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]

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]

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 prototype

int main( int argc, char *argv[] )

{

TowersOfHanoi(3,1,3,2); ///non-recursive call

return 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 call

cout << sourcePeg << " --> " << destinationPeg << endl;

TowersOfHanoi(disks-1,tempPeg,destinationPeg, sourcePeg );//recursive call

}

////end

Please some body explain to me how this program use the stack to implement it functions.

[deepzero]

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...