Pascal's Triangle with Recursion in JS - Explanation Asked

Question

I have checked the other topics. It looks like these issues mainly concerns C++ and Python devs but wanted to ask to have a better understanding about recursion.

A Pascal Triangle is a triangle that consists of 1's on the edges and the sum of the upper two numbers in the interior:

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
        .
        .
        .            

Here is the code:

function pascalTriangle(row, col) {
    if (col === 0) {
        return 1;
    } else if (row === 0) {
        return 0;
    } else {
        return pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1);
    }
}

Code doesn't draw a diagram but only returns the inner most value in the triangle.

My question is about the recursive else statement:

how does the call stack execute else statement? Logic behind that line actually?

bonus if you are eager to help:

how to get your code move on to the next line when finished executing for that specific line?

Answer 1

Let's start with a rather general explanation and get more specific along the way to gain a better intuition on recursion. Recursion is the strategy to break down a problem into its smallest instances and than compose these instances one by one to get the solution.

What are the smallest instances of the given problem? 0 and 1, because these are returned by the two base cases. Every recursive step will eventually yield one of these base cases. Since we have two distinct recursive steps pascalTriangle(row - 1, col) and pascalTriangle(row - 1, col - 1), the following permutations are probably possible:

0 + 0
0 + 1
1 + 0
1 + 1

These operations represent the smallest instances of the given problem. Please note that you can substitute recursive steps with the base cases, but what you get are only snapshots of the recursive algorithm. The big picture is a bit more involved.

There is another important property of recursive algorithms we haven't spoken about yet: They create nested computational structures. Nesting is inherent to recurison. Let's visualize the nested structure created by pascalTriangle. We can either do this manually with substitution or autmatically by adapting the function:

function pascalTriangle(row, col) {
    if (col === 0) {
        return 1;
    } else if (row === 0) {
        return 0;
    } else {
        return `(${pascalTriangle(row - 1, col)} + ${pascalTriangle(row - 1, col - 1)})`;
    }
}

console.log(pascalTriangle(4, 2));
// ((((0 + 0) + (0 + 1)) + ((0 + 1) + 1)) + (((0 + 1) + 1) + 1))

This is a synthesized nested structure which is equivalent to the intermediate structure actually created by your recursive computation. If you sum it up you get 6, which is the expected result.

Maybe you have already noticed that the permutations I listed above are wrong. Only 0 + 0 and 0 + 1 are possible with the given algorithm.