How is this recursion working?

Question

Now i was reading at MDN functions section, and i was reading this example about recursion, which was:

    function foo(i) {
    if (i < 0)      //1
    return;
    console.log('begin:' + i);   //2
    foo(i - 1);   //3
    console.log('end:' + i); //4
}
foo(3);

So what I would normally expect of calling the recursive function foo with an argument of 3 is that it goes to line 1 checks that condition which is at the beginning not gonna hold so it continues to line 2 and logs the ("begin: 3") then it goes to line 3 where recursion happens and that will make it go back to the line 1 and go through the same flow of processes, which should lead to ("begin: 2"), ("begin: 1"), ("begin: 0"), then it should stop so that it won't clog ("begin: -1"), that indeed happens in MDN example but somehow it logs is one more time but reversibly like this:

// Output:

// begin:3
// begin:2
// begin:1
// begin:0
// end:0
// end:1
// end:2
// end:3

My Questions:

in which sense after that (i = -1) and the function returns, the function is not exiting the function and continue to line number 4?
how is (i) increasing again, i see no loop or recursion that is increasing the value of (i) again so that it logging again from 0 to 3??

Possible duplicate of [Understanding how recursive functions work](http://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) — Andreas, Oct 14 '16 at 10:03
Doing i - 1 doesn't change the original value. Foo(3) still has i = 3, foo(2) still has i = 2, etc. — Alexey Soshin, Oct 14 '16 at 10:05
Have you seen this question http://stackoverflow.com/questions/40040362/how-is-this-recursion-working :D — TommyBs, Oct 14 '16 at 10:22

score 1 · Answer 1 · answered Oct 14 '16 at 10:13

Here is what is happenning in your case :

// foo(3) called
console.log('begin:3');
foo(2)
    console.log('begin:2');
    foo(1)
        console.log('begin:1');
        foo(0)
            console.log('begin:0');
            foo(-1)
                return;
            console.log('end:0');
        console.log('end:1');
    console.log('end:2');
console.log('end:3');

1) When you have (i == -1), the function is actually exiting with the return, but then keep executing the code in the parents functions (see point 2) )

2) When you call foo(-1), you call return, so it means that you get back to your parent caller and keep executing the following code.

score 0 · Answer 2 · answered Oct 14 '16 at 10:06

0

your function doesn't terminate before the result of the inner function call is there.

1) is the abort condition, it tells the function when to stop

2) its not increasing, its going further, because the result of the foo(i-1) call is there

answered Oct 14 '16 at 10:06

MemLeak

4,456
4
45
84

score 0 · Answer 3 · answered Oct 14 '16 at 10:06

Whenever a recursion occurs, the control perpetually remains at the top level. So although, the function goes through n number of inner levels, a return statement from one of the inner called functions would merely return to its immediate parent level.

In this case: i=3 was at the top level, then 2 and then 1 and then 0. As the return was fired at i=-1, it was bubbled back to its parent 0 level. The next return bubbled it up to its parent i=2 , and then i=3.

Do mark as answer if you're satisfied.

score 0 · Answer 4 · answered Oct 14 '16 at 10:12

Your function does exactly what you have told it to do:

print begin:3
do everything that foo(3-1) does
print end:3

Every call to a function wait for it to finish before resuming to the next line. If it's the same function it's the same. The version of the function that calls is not intervened with the one it calls so they are separate as if they were separate functions

Imagine this function:

function foo(i) {
    console.log('begin:' + i);  //1
    console.log('end:' + i);    //2
}

Now the first console.log might be a recursive function. You don't know and shouldn't have to know. It does it's job and returns. You don't question why it continues to line 2 so I guess you give recursive function more mystery than it deserves.

score 0 · Answer 5 · answered Oct 14 '16 at 10:16

function foo(i) {
    if (i < 0){      //1
       return;
    }
    console.log('begin:' + i);   //2
       function foo(i-1) {
       if (i-1 < 0){      //3.3.1
          return;
       }
       console.log('begin:' + i-1-1);   //3.3.2
          function foo(i-1-1) {
          if (i-1-1 < 0){      //3.3.1
             return;
          }
          console.log('begin:' + i-1-1);   //3.3.2
          function foo(((i-1) - 1)-1){};   //3.3.3
          console.log('end:' + i-1-1); //3.3.4
          }
       console.log('end:' + i-1); //3.4
       }
    console.log('end:' + i); //4
}

foo(3)

Let's pretend i is alwyas 3!

This is what happens:

going into //2 and log 3
going into //3.2 and log 2
going into //3.3.2 and log 1
going into //3.3.3 and do the same stuff and log 0
going into imaginary //3.3.3.4 and log 0 because the parameter of //3.3.3 is 0
going into 3.3.4 and log 1
going into 3.4 and log 2
going into 4 and log 3

How is this recursion working?

5 Answers5