how does recursion retain value even after some cycle

Question

Can some one explain the execution of this program . OUTPUT is: 1 2 3 4 3 2 1

how does function retain value 3,2,1 in the end

main(){
   int h=0;
    g(h);
}
 g(int n){
    n++;
    printf("%d\n",n);
    if (n ==4)return 88;
    g(n);
    printf("%d\n",n);
}

It doesn't. Step through the code line by line in a debugger (stepping into the recursive calls) and it should become clear. — Some programmer dude, Jan 31 '19 at 12:12
The most important thing to understand is that `g(int n)` means a new `n` is created every time the function is called. The first time `n==0`, then `n++` and in the next (recursive) call `n==1`, then `n++`, et cetera. — Paul Ogilvie, Jan 31 '19 at 12:19

score 3 · Accepted Answer · answered Jan 31 '19 at 12:28

You are getting the above output because at the 8th line of your code you are calling the function agian recursively so the remaining code after the 8th line is saved in the call stack in your memory. So, when you get the output 1 2 3 4, the remaining code that is left (in call stack) is executed hence you are getting this output.

below is the call stack of your program when n = 0 the stack will place 1 |___| |___| |_1_| when n = 1 the stack will place 2 |___| |_2_| |_1_| when n = 2 the stack will place 3
|_3_| |_2_| |_1_| when n = 4 the stack will not place anything as it encounters the return statement now, we have some values in our stack

so the program starts popping the top most value in stack (here n = 3) and continue the execution where it left off (i.e it will print the value) and this process will go on until the stack is empty.

NOTE: You can visit this video to understand more effectively about recursion https://www.youtube.com/watch?v=Mv9NEXX1VHc

score 1 · Answer 2 · answered Jan 31 '19 at 12:15

 g(int n){
    n++;
    printf("%d\n",n); // n=1 print 1 & call g(n) with 1 now g(1) make its own n=2 print 2 & call g(2) 
    //... print 3 & call g(3) becomes  4  print 4 return 88 
    if (n ==4)return 88;


    g(n);

     // now after the return we get back to the 3rd call that called g(3) 
     //so it print 3 at the end 3 ends 
     //we go back to the one that called g(2) so we print 2 at the end... & same for 1
    printf("%d\n",n);
}

Support Ukraine · Answer 3 · 2019-01-31T12:51:06.010

In C the function arguments acts as local variables inside the function. Further C uses call-by-value which means that the value of variable used by the caller as argument is copied to the functions argument variable. Consequently the two variables are completely independent variables.

Consider this code:

void foo(int x)
{
    x++;
    printf("%d", x);
}

void bar(int y)
{
    y++;
    printf("%d ", y);
    foo(y);
    printf("%d", y);
}

bar(0);

This will output "1 2 1"

Most people find that it's obvious that changes to x will not change y. They are by name two different variables. So no surprise in that.

If we change the code to use the same name for variables - like:

void foo(int x)
{
    x++;
    printf("%d", x);
}

void bar(int x)
{
    x++;
    printf("%d ", x);
    foo(x);
    printf("%d", x);
}

bar(0);

The output is still "1 2 1"

Simply because the variable x inside foo is another variable than x inside bar. The only relation ship they have is that x inside foo is initialized with a copy of the value of x inside bar. No matter what kind of change you make to x inside foo it will/can not change x inside bar.

Exactly the same goes for the recursion. Each function call creates its own variable n - completely independent of the n variable in previous calls.

Most implementations use a stack for implementing this functionality. Do a search for "stack frame" to get more information. Also see Explain the concept of a stack frame in a nutshell

score 1 · Answer 4 · answered Jan 31 '19 at 12:49

You can read above answers they are pretty good, but here is another way to get you head around it. Simplest answer is the same way that caller function retains its value when calling any function. For example if you have:

int main (void) {
    int a = 5;
    fun1 (a);
}

void fun1 (a) {
    fun2 (a);
    printf("%d\n", a); // output would be 5
}

void fun2 (int a) {
    a+=1;
    fun3 (a);
    printf("%d\n", a);
}

void fun3 (int a) {
    a+=1;
    printf("%d\n", a);
}

So fun1 () would print out 5, fun2 () 6 and fun3() 7. Recursion function is similar to above from perspective of caller and called function, instead of calling function with different name it is calling the function with same name, or in other words it is calling itself.

Look at this code:

void recFun (int a) {
   if (a > 6)
       printf("%d\n", a);

   recFun (a + 1);

   printf("%d\n");
}

Some people when I was in school would rewrite above to following (on a piece of paper of course this would yell at you if you try to compile it):

void recFun (int a) {
   recFun (a + 1);

   printf("%d\n");
}

void recFun (int a) {
   recFun (a + 1);

   printf("%d\n");
}

void recFun (int a) {
   printf("%d\n");
}

how does recursion retain value even after some cycle

4 Answers4