Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Pascal's Triangle Recursive Javscript

I need some help understanding this solution for pascal’s triangle recursive function in javascript. This code is a solution to the following problem on LeetCode: https://leetcode.com/problems/pascals-triangle/

What I am not understanding is the line newRow[i] = prevRows[numRows - 2][i - 1] + prevRows[numRows - 2][i];

What I’m assuming is that we’re adding the two above elements to make the bottom element in the triangle which is obvious. But what kind of data structure is this? What is prevRows a type of?

Also, I’m having trouble understanding the recursion. It seems if I input a number like 5, the function is just gonna call itself 4 times until it reaches a base case of 1 and then it will return 1. I’m not understanding how the triangle is being made.

var generate = function(numRows) {
    if (numRows === 0) {
        return [];
    }
    if (numRows === 1) {
        return [[1]];
    }
    
    let prevRows = generate(numRows - 1);
    let newRow = new Array(numRows).fill(1);
    
    for (let i = 1; i < numRows - 1; i++) {
        newRow[i] = prevRows[numRows - 2][i - 1] + prevRows[numRows - 2][i];
    }
    
    prevRows.push(newRow);
    return prevRows;
};
Tags:

2

Answers


  1. 0

    Sometimes, it helps if you clean up the code a bit and use more meaningful variable names.

    function makeTriangle(size) {
    if (size === 1) {
        return [[1]];
    }

    let smallerTriangle = makeTriangle(size - 1);
    let lastRow = smallerTriangle.at(-1);
    let newRow = [];

    newRow.push(1);

    for (let i = 0; i < lastRow.length - 1; i++) {
        newRow.push(lastRow[i] + lastRow[i + 1])
    }

    newRow.push(1);

    return smallerTriangle.concat([newRow]);
}

console.log(makeTriangle(7).map(String))

    Is that more understandable to you? If not, try to run it step by step in a debugger and watch the variables.

    Login or Signup to reply.
  2. 0

    You write: "…and then it will return 1": but that’s not the end: every recursive call has a return value, so there is not only one return of [[1]]; there are as many returns as recursive calls. And each call returns a 2D array (the pyramid) that has one more row than the previously executed return.

    Let’s visualise the process for when the function is called with argument 3. In the following table, a column represents one execution of the function, where execution starts in the first column. When a recursive call is made, we move to the column at the right of it, and when a return is executed we return to the left-neighboring column. The rightmost column is reserved for representing the current 2D array, which starts its existence at the base case, and then is extended by push calls (all local prevRows variables get to reference the same 2D array that "grows"):

    generate(3) generate(2) generate(1) prevRows
    generate(2) – – –
    generate(1) – –
    return [[1]] –
    let prevRows = [[1]] – [[1]]
    let newRow = [1, 1] – [[1]]
    prevRows.push([1, 1]) – [[1], [1,1]]
    return prevRows – [[1], [1,1]]
    let prevRows = [[1], [1,1]] – – [[1], [1,1]]
    let newRow = [1, 1, 1] – – [[1], [1,1]]
    newRow[1] = 1 + 1 = 2 – – [[1], [1,1]]
    prevRows.push([1, 2, 1]) – – [[1], [1,1], [1,2,1]]
    return [[1], [1,1], [1,2,1]] – – [[1], [1,1], [1,2,1]]

    I hope this clarifies it.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search