Ad

How And Why Recursion Works And What Internally Goes On

- 1 answer

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 ?
Ad

Answer

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

Ad
source: stackoverflow.com
Ad