JavaScript recursion, understanding in detail

Question

I am not able to understand how this recursion is going to work. Specifically, I'm not able to get a clear idea about how the last console ('end'---) is getting executed. Please provide guidance. Please help me on the execution part. I am not understanding how it is forming the output

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

foo(3);

i am not able to understand when and how console.log('end: ' + i) statement is executed. I would really appreciate it. Thanks in advance. — Hemant, Feb 08 '17 at 13:38
If you want to add further clarifications to your question, you can [edit] it. — James Thorpe, Feb 08 '17 at 13:38
If you are having trouble visualizing how the recursion works, draw a tree to help, remember that `i` is a copy of a variable and not the same one, so the call to `foo(i - 1)` will not change the value of i for the call to the `console.log('end: ' + i);` — Adam M., Feb 08 '17 at 13:40
As per my understanding console.log('end' + i) will never be executed because it is executed after foo(i-1) . I am not sure when and how it is executed. Could you please clarify on this ?? — Hemant, Feb 08 '17 at 13:44
@Hemant your understanding is wrong - when `foo(i - 1)` finishes, the flow goes back to the line following, i.e. `console.log('end')` — Alnitak, Feb 08 '17 at 13:51
See http://stackoverflow.com/questions/717725/understanding-recursion — GôTô, Feb 08 '17 at 14:00
If you found any of the answers useful please consider up-voting them. If you found an answer helped solved your question, please also consider accepting it as an answer too :) — Pineda, Apr 07 '17 at 14:05

Pineda · Answer 1 · 2017-02-08T14:00:57.910

Explanation of how this function executes:

Let's trace out what happens when you invoke this method and pass 3 as an argument:

foo(3);
 // (3<0) false, so skip the return
 // Log out: 'begin: 3'
  //foo (2);
  // (2<0) skip return;
  // Log out: 'begin: 2'
    //foo(1);
      // (1<0) skip return;
      // Log out: 'begin: 1'
      //foo(0);
        // (0<0) false, skip return;
        // Log out: 'begin: 0'
        //foo(-1);
        //(-1 < 0) true!!! 
        //return undefined
      // Log out: 'end: 0'
      //return undefined
    //Log out: 'end: 1'
    //return undefined
  //Log out: 'end: 2'
  //return undefined
//Log out: 'end: 3'
<---return undefined

Actual output:

begin: 3
begin: 2
begin: 1
begin: 0
end: 0
end: 1
end: 2
end: 3
undefined

score 2 · Answer 2 · edited Feb 08 '17 at 13:56

2

First iteration: foo(3) so i=3, then foo(2) is called, i=2, then i=1 and i=0. Now foo(-1) is called. The if condition is now true, so it returns in foo(0) call, where console.log is executed with i=0. Then i=1, i=2, i=3.

So you will have:

begin 3
begin 2
begin 1
begin 0
end 0
end 1
end 2
end 3

edited Feb 08 '17 at 13:56

mplungjan

169,008
28
173
236

answered Feb 08 '17 at 13:46

mychemicalro

232
3
21

I understand partially above call what i did not understand from the explanation is still how the console.log('end' + i) is executing , i am new to javascript but still i think , it will never execute. i am wrong but i still did not understand it. – Hemant Feb 08 '17 at 13:56
You are wrong. consider this: foo(3) prints "begin 3" then it calls foo(2). That means that foo(3) still not finish to execute! foo(3) still not returned! so now its foo(2) executing, and then foo(1) and so on since if condition becames true! when it is true, so when (1<0) then and only then foo() returns! that means foo(-1) returns and gets back to foo(0) and then the last instruction is executed, then foo(1) and so on to foo(3) – mychemicalro Feb 08 '17 at 13:59
Thanks i understand a bit now. – Hemant Feb 08 '17 at 14:15
Try to see something about recursion – mychemicalro Feb 08 '17 at 14:17
Thanks i am understanding now. – Hemant Feb 08 '17 at 14:30

Adam M. · Answer 3 · 2017-02-08T13:48:51.790

1

When you call foo(3) what we see is this:

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

what happens in the code is this:

begin: 3
//foo is called, foo(2)
//start of foo(2)
begin: 2
//foo is called, foo(1)
//start of foo(1)
begin: 1
//foo is called, foo(0)
//start of foo(0)
begin: 0
//foo is called, foo(-1)
//start of foo(-1)
//if statement condition is true, returns, ending the recursion chain
//thread returns back to the foo(0) method, logs i
end: 0
//thread returns back to the foo(1) method, logs i
end: 1
//thread returns back to the foo(2) method, logs i
end: 2
//thread returns back to the foo(3) method, logs i
end: 3

edited Feb 08 '17 at 13:48

answered Feb 08 '17 at 13:47

Adam M.

1,023
1
10
21

I still did not understand, how thread return back to foo(0) and printing end :0 – Hemant Feb 08 '17 at 13:58
don't think of calling foo like it being the end of the method, when you call foo it is the same thing as calling console.log, it performs the operation that are assigned to `console.log` and then does the next piece of code. in this case it calls itself. really work through it how you think a computer would do it and you'll get it – Adam M. Feb 08 '17 at 14:00

JavaScript recursion, understanding in detail

3 Answers3