Why recursion occurs in reverse
The question is, does the function pause at the line where the function is called again or does it executes fully and then come back to that line (where the same function is called).
I also have this example which shows that recursion occurs in reverse (I guess each inner function keep reference to its outer function and execution occurs in reverse to normal order).
Please go in much details as possible.
function func(n) {
if(n > 0) func(n-1)
console.log(n)
}
func(10) // 1,2,3,4,5,6,7,8,9,10
// while I was expecting 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
I would suggest to use debugger tools in chrome to trace the codes execution. Recursion does happen backwards because it has to meet your base case in order to exit. Every time it does not meet your base case the current running function is put in call stack (in JS). In you case func(n-1
gets called and previous func
is put in call stack. Once your base case is met, your func
s that are in call stack start to continue running (from leftover line -> console.log
). Since the nature of stacks is Last In First Out (LIFO), you functions run in reverse.
function func(n) {
console.log(n) //output 3 2 1
if(n > 0)
func(n-1)
console.log(n) //output 1 2 3
}
func(3) //Taking small digit for quick explanation
When func(3)
is called from main()
, memory is allocated to func(3)
and a local variable test
is initialized to 3
and statement 1 to 4 are pushed on the stack as shown in below diagram.
It first prints 3
. In statement 2, func(2)
is called and memory is allocated to func(2)
and a local variable test
is initialized to 2
and statement 1 to 4 are pushed in the stack.
Similarly, func(2)
calls func(1)
and func(1)
calls func(0)
.
func(0)
goes to if
statement and it returns to func(1). Remaining statements of func(1)
are executed and it returns to func(2)
and so on.
In the output, value from 3 to 1 are printed and then 1 to 3 are printed. The memory stack has been shown in below diagram.
To get your expected output, just print using console.log
before making the recursive call:
function func(n) {
console.log(n)
if(n > 0)
func(n-1)
}
func(10) // 1,2,3,4,5,6,7,8,9,10
Regarding your question about whether the recursive function "pauses", or keeps going, the answer is that when it makes another recursive call, it stops in its tracks until that call returns. This is the reason why your current code is printing 1, 2, ..., 10. This happens because each function call stops when making the recursive call, and only wakes up again after that call has completely finished. This means that the smallest base case value gets printed first, then larger subsequent values get printed in reverse order.