CODEWITHSUNDEEP
javascriptrecursion
thedoomer1000
thedoomer1000

Reputation: 73

Dont understand the next iteration for recursion

I'm learning to work with recursion and so far it went well with basic examples. However I want to calculate the factorial, but I don't understand what happened step-by-step. If I do it imperatively I understand it but I fail on this example:

return x * fac(x-1); gives me back 5 * 4, so far soo good, but what happens now? Does it mean it become 20 now? So my next iteration would be then 20 * 19?

      const fac = (x) => {
        if(x <= 1) {
          return x;
        }
        return x * fac(x-1);
      };
      console.log(fac(5)); // 120

Upvotes: 0

Views: 71

Answers (2)

thedoomer1000
thedoomer1000

Reputation: 73

I think i understand that part now and the difference between 4 and fac(4). The steps look like:

5. 5 *       // ()
4. 4 *       // (20)
3. 3 *       // (60)
2. 2 *       // (120)
1. 1 *       // (120)

However, I have another example which i cant resolve step by step, while i can see the logic in the imperatively programming.

let fibo = (x) => {
  if(x<=2) {return 1;}
  return fibo(x-1) + fibo(x-2);
};
console.log(fibo(4));  //3

I cant resolve step by step what return fibo(x-1) + fibo(x-2); values this gives me each step. On the imperatively programming it is


function fibonacci(num){
  var a = 1, b = 0, temp;

  while (num >= 1){
    temp = a;
    a = a + b;
    b = temp;
    num--;
  }

  return b;
}
console.log(fibonacci(4);  // 3

where the steps would be like


4. b = 1
3. b = 1
2. b = 2
1. b = 3

Upvotes: 0

bryan60
bryan60

Reputation: 29335

just walk through the logic.

1. fac(5) yields 5 * fac(4)
2. fac(4) yields 4 * fac(3)
3. fac(3) yields 3 * fac(2)
4. fac(2) yields 2 * fac(1)
5. fac(1) yields 1

substituting from bottom to top, you get

fac(5) = 5 * 4 * 3 * 2 * 1

Upvotes: 1

Related Questions