Doubt in recursion 1

[anvartk]

How does the successive values
are stored in recursion(internal)?

 

[rbobbitt]

Hi,

Generally, it's done in the form of a "stack" where each value is placed on top of the stack (a "push&quot and then each value is removed from the stack (a "pop&quot when the function returns in last-in-first-out order (LIFO).

As far as recursion is concerned, this implies that your program may run out of stack space as the stack isn't "popped" until the function stops recursing. Unfortunately (AFAIK), there's no portable way to determine that you are about to run out of stack space. Fortunately, running out of stack space isn't typically anything to worry about unless your function is /deeply/ recursive or memory is at a premium.

The /exact/ method used varies from implementation to implementation, your compiler docs may have info on how yours does it.

HTH,

Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts

 

[vkavith]

Russ is prefectly right. Also to add, a return call in a recursive function will return to its previous call and not straight away to the main program where the function is first called. Thus

int main ()
{
myfunc (10);
}

void myfunc (int i)
{
if (i == 1)
return;
myfunc (--i)
}

Notice here that the return in myfunc will not return to the main program. It will return to its previous call which is incidently its previous call.

Hope I d'nt confuse.
Sriks

 

[rbobbitt]

Sriks, I'm not sure I understand what you're saying. When you hit the return in myfunc() control passes back to main().

Here's a modified version of your program (with output added) and what the results were on one of my machines:

/* Begin rec.c */
#include <stdio.h>
void myfunc(int);

int main ()
{
puts(&quot;about to recurse (in main)&quot;
myfunc(10);
puts(&quot;end of recursion (in main)&quot;
return 0;
}

void myfunc (int i)
{
if (i == 1) {
puts(&quot;condition met, returning (in myfunc)&quot;
return;
}
printf(&quot;recursing (i==%d) (in myfunc)\n&quot;,i);
myfunc (--i);
}

/* End rec.c */

Russ -143- uname -a
SunOS newsrhq 5.5.1 Generic_105428-01 sun4u sparc SUNW,Ultra-5_10
Russ -144- gcc -v
Reading specs from /usr/local/lib/gcc-lib/sparc-sun-solaris2.5.1/2.95.2/specs
gcc version 2.95.2 19991024 (release)
Russ -145- gcc rec.c
Russ -146- ./a.out
about to recurse (in main)
recursing (i==10) (in my func)
recursing (i==9) (in my func)
recursing (i==8) (in my func)
recursing (i==7) (in my func)
recursing (i==6) (in my func)
recursing (i==5) (in my func)
recursing (i==4) (in my func)
recursing (i==3) (in my func)
recursing (i==2) (in my func)
condition met, returning (in my func)
end of recursion (in main)




Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts

 

[Nosferatu]

@Rbobbit

I suggest you to modify a little bit the recursive function and add a printf statament...

When hitting return, the function next called it is not main! When calling a function, the function address is saved as well as the Instruction pointer (IP), so, when hitting return, the program execution will continue in the last function saved on the stack, from the IP+1.

Try:

void myfunc (int i)
{
        if (i == 1) {
                puts("condition met, returning (in yfunc)");
                return;
        }
        printf("recursing (i==%d) (in myfunc)\n",i);
        myfunc (--i);
        printf("Still in the recursive function! \n");
}

and you will see &quot;Still in the recursive function!&quot; printed 9 times or so before returning to main!

 

[rbobbitt]

Now I understand what sriks was saying! Thanks for the tip, that's quite interesting!

Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts

 

[vkavith]

rbobbitt, if u are aware of the &quot;Tower of Hanoi&quot; problem, it is a very good 'practical' example of implementing this using the recursive method. For a more simple case think of the typical factorial solution.

Sriks