how and why recursion works and what internally goes on

Question

This is a simple code for factorial

console.log(`5 fact = ${fact(5)}`)

function fact(num){
        if(num == 0) {
            return 1;
        }else {
            console.log(`${num} * fact(${num} - 1)` )
            //console.log(num * fact(num - 1))
            return num * fact(num - 1)
        }
    }

i got output when i comment second console inside factorial

5 * fact(5 - 1)
4 * fact(4 - 1)
3 * fact(3 - 1)
2 * fact(2 - 1)
1 * fact(1 - 1)
5 fact = 120

when i uncomment it i got to know some weird things going on inside.

console.log(`5 fact = ${fact(5)}`)

function fact(num){
        if(num == 0) {
            return 1;
        }else {
            console.log(`${num} * fact(${num} - 1)` )
            console.log(num * fact(num - 1))
            return num * fact(num - 1)
        }
    }

2
1 * fact(1 - 1)
1
24
3 * fact(3 - 1)
2 * fact(2 - 1)
1 * fact(1 - 1)
1
2
1 * fact(1 - 1)
1
6
2 * fact(2 - 1)
1 * fact(1 - 1)
1
2
1 * fact(1 - 1)
1
120
4 * fact(4 - 1)
3 * fact(3 - 1)
2 * fact(2 - 1)
1 * fact(1 - 1)
1
2
1 * fact(1 - 1)
1
6
2 * fact(2 - 1)
1 * fact(1 - 1)
1
2
1 * fact(1 - 1)
1
24
3 * fact(3 - 1)
2 * fact(2 - 1)
1 * fact(1 - 1)
1
2
1 * fact(1 - 1)
1
6
2 * fact(2 - 1)
1 * fact(1 - 1)
1
2
1 * fact(1 - 1)
1
5 fact = 120

Can anyone explain me.

Where the temporary result will get saved ?
according to console and code logic it should return 1. But, why it return 120 ?
what internally happening here ? Is their any limits we need to consider to choose with recursion ?

Does this answer your question? [Understanding recursion](https://stackoverflow.com/questions/717725/understanding-recursion) — dloeda, Jan 28 '20 at 07:55
Calling the recursive function when logging the value messes up the recursion. — Teemu, Jan 28 '20 at 08:04
@dloeda Where the temporary result will get saved ? That I'm not getting. everyone trying to explain how recurrsion works. But i'm looking for internal things. — shiv, Jan 28 '20 at 08:14
https://developer.mozilla.org/en-US/docs/Glossary/Call_stack . And yes, call stack has an implementation dependent limit. My previous comment explains the odd results you're getting. — Teemu, Jan 28 '20 at 08:27
@Teemu Thank you very much atleast for answering. Frankly saying i'm still a college student. So, Can you little bit brief your answer In answer section itself. — shiv, Jan 28 '20 at 08:34
I think I can't explain call stack better than it is explained at MDN. You could try to implement the same recursion without functions, by using nested loops instead and keeping book of the results in your own "call stack", that might help you to understand how it works. — Teemu, Jan 28 '20 at 08:37

score 3 · Accepted Answer · edited Jan 28 '20 at 09:27

Ok, I will try to answer your Question.

Firstly your code is little bit messed up. So change it

console.log(`5 fact = ${fact(5)}`)

function fact(num){
        console.log(`num = ${num}`)
        if(num == 0) {
            console.log(`----confusing is it ## why i didn't returned 1 ##-----`)
            return 1;            
        }else {
            console.log(`${num} * fact(${num} - 1)`)
            n = num * fact(num - 1);
            console.log(n); 
            return n;
        }
    }

when you run this the Output you will get

num = 5
5 * fact(5 - 1)
num = 4
4 * fact(4 - 1)
num = 3
3 * fact(3 - 1)
num = 2
2 * fact(2 - 1)
num = 1
1 * fact(1 - 1)
num = 0
----confusing is it ## why i didn't returned 1 ##-----
1
2
6
24
120
5 fact = 120

Explanation

when ever you call same function i.e fact(num - 1) the next lines of code will not execute untill the equation is solved. Thats why untill you get into
```
num = 1
1 * fact(1 - 1)
num = 0
```
you didn't get calculated answer's like 1 24 120 ... etc.
When num = 0 it went inside confusing part and return's 1 to its calling function fact(1 - 1). Don't get confused it will not return 1 to main calling function 5 fact = ${fact(5)}.
Now, 1 * fact(1 - 1) becomes 1 * 1 which is equal to 1
Next thing in stack memory is 2 * fact(2 - 1) which becomes 2 * 1 as fact(2 - 1) is 1 * fact(1 - 1) which is equal to 2.
Next in stack is 3 * fact(3 - 1) and fact(3 - 1) is 2 * fact(2 - 1) is 2 there fore 3 * 2 i.e 6
Like this all calculations happen until it comes back to first thing in stack i.e 5 * fact(5 - 1) which is equal to 5 * 24 which is 120.

Finally once it solves and remove every equation in memory. It returns result to calling statement
console.log(`5 fact = ${fact(5)}`)

Important

Look i don't know about memory think It might be wrong or right i don't know Coz I'm not a computer science person
But I'm damn sure the flow i mentioned is what happening internally.

And of Course we need to consider the call stack limitations

how and why recursion works and what internally goes on

1 Answers1