I'm learning the recursion concept in js, I got a very basic question of the base code returning problem.

function factorial(n) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n - 1);  
}

So this is a simple factorial example of explaining the recursion.

factorial(5) = 120

My question is, why it's not returning 1 when the n reaches 1? After the return inside the if statement, the second return will continue to run? And if it return 1, the second return continue to run and it will do 5 * 1 forever (let's say n reaches 5)???

CodePudding user response：

A good way of analyzing recursion is by using a simple situation, and think how the recursion will unfold.

Lets say n = 3.

function factorial(n) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n - 1);  
}

console.log(factorial(3));

So, the following iterations will happen:

fac(3)   == 3 * fac(3-1)
fac(3-1) == 3-1 * fac(2-1)
fac(2-1) == 2-1 * 1

The condition that makes the recursion unfold and start returning is n == 1, so when that happens, the last function call will return 1 instead of calling itself again.

But the actual result will be the sum of all returned operations: (3 * ((3-1) * ((2-1) * 1)))

So, factorial(5) returns 120 because: (5 * ((5-1) * ((4-1) * ((3-1) * ((2-1) * 1))))) == 120.

CodePudding user response：

I made a small example, adding some log's. The attribute indent was added to help on logs indentation, and for better understand what's happen.

On recursive calls (like on non recursive calls), when outer function calls the inner function, the current variables are stored somewhere on memory (on one stack), and then call the function.

When the inner function returns, the values will be restored.

If you see the log's of my example, the parameter n decrease the value on each call, but was restored after the inner function returns.

Answering to your questions:

My question is, why it's not returning 1 when the n reaches 1?

• when the n reaches 1, the function returns 1, but that result will applied on de factorial(2), that are waiting at that moment for the result, and so on.

After the return inside the if statement, the second return will continue to run?

• Yes, the second if statement will continue to run, but it's like on other instance, that was waiting for the result.

And if it return 1, the second return continue to run and it will do 5 * 1 forever (let's say n reaches 5)???

• No. The n will be multiplied with the result of next call (the outer call waits for the inner call):

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

function factorial(n, indent) {
    if (!indent) indent = '';
    console.log(indent 'BEGIN: factorial(' n ')');
    if (n === 1) {
        console.log(indent 'END: factorial(' n '): 1');
        return 1;
    }
    let factorialNMinus1 = factorial(n - 1, indent   '    ');
    let result = n * factorialNMinus1 ;
    console.log(indent 'END: factorial(' n '): '   n   ' * '   factorialNMinus1   ' = '   result);
    return result;  
}

console.log('result = '   factorial(5));