Printing out Pascal's Triangle in row-major format

Question

Here's the problem statement:

Given an integer value, print out Pascal's Triangle to the corresponding depth in row-major format:

Input Sample:

6

Output Sample:

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

I need some practice with recursion, so I tried that approach:

var pascalDepth = parseInt(line, 10); //The input integer is provided on a single line as a text value, so this handles it.
var testTriangle = pascalTriangle(pascalDepth);
var output = [];

for(var i = 0; i < testTriangle.length; i++){
    for(var j = 0; j < testTriangle[i].length; j++){
        output.push(testTriangle[i][j]);
    }
}

console.log(output.join(" "));   

function pascalTriangle(totalLines, triangle) {
    if (typeof triangle === 'undefined') {
        triangle = [];
    }

    if (triangle.length === totalLines) {
        return triangle;
    }

    if (triangle.length > 0) {
        var triangleLine = [];
        for (var i = 0; i < triangle.length; i++) {
            if (typeof triangle[triangle.length - 1][i - 1] === 'undefined') {
                triangleLine.push(1);
            } else {
                triangleLine.push((triangle[triangle.length - 1][i - 1] + triangle[triangle.length - 1][i]));
            }
        }
        triangleLine.push(1);
        triangle.push(triangleLine);
    } else {
        triangle.push([1]);
    }
    return pascalTriangle(totalLines, triangle);
}

Answer 1

Like the Fibonacci sequence, calculating Pascal's triangle recursively using a pure functional approach wouldn't be very efficient, since you would repeatedly compute many of the entries.

You've implemented a recursive solution with memoization, which is smarter. However, with memoization, the solution is stylistically iterative. Consider the following function, which behaves identically to yours, but is written in a more straightforward manner:

function pascalTriangle(totalLines) {
    var triangle = [];
    while (triangle.length < totalLines) {
        if (triangle.length > 0) {
            var triangleLine = [];
            for (var i = 0; i < triangle.length; i++) {
                if (typeof triangle[triangle.length - 1][i - 1] === 'undefined') {
                    triangleLine.push(1);
                } else {
                    triangleLine.push((triangle[triangle.length - 1][i - 1] + triangle[triangle.length - 1][i]));
                }
            }
            triangleLine.push(1);
            triangle.push(triangleLine);
        } else {
            triangle.push([1]);
        }
    }
    return triangle;
}

You could consider your "recursion" to be a fancy goto. Alternatively, you could conclude that Pascal's triangle does not lend itself to recursion.

---

That said, your implementation could be more compact. Think of deriving the next line this way:

  [ , 1, 3, 3, 1]
+ [1, 3, 3, 1,  ]
—————————————————
  [1, 4, 6, 4, 1]

Then, you can use higher-level thinking: make two arrays with the appropriate offset, and find the sums of the corresponding elements.

function pascalTriangle(totalLines, triangle) {
    // Helper function to add corresponding elements of two arrays
    function sum(a, b) {
        return a.map(function(_, i) {
            return a[i] + b[i];
        });
    };

    if (triangle == null) {                 // Initial call with just one parameter
        triangle = [[1]];
    }
    if (totalLines === triangle.length) {   // Final case
        return triangle;
    }
    var prevLine = triangle[triangle.length - 1];
    var nextLine = sum([0].concat(prevLine), prevLine.concat([0]));
    return arguments.callee(totalLines, triangle.concat([nextLine]));
}

I've used arguments.callee for the function to refer to itself, so that if you rename the function (or make it anonymous), it can still work.

Answer 2

I have this implementation right off the top of my head and it doesn't use recursion. It's a plain loop that creates the current row with the previous row.

Here's the jsPerf results as well, with improvements in performance in some browsers, double especially Safari and Firefox.

//we need our depth input, and our storage array
var depth = 6,
    output = [];

//we have a function that calculates the row using the existing triangle
function triangulate(triangle, rowIndex) {

    //we declare variables up the top of the scope like how JS sees it
    //this also makes clear what variables are in the scope
    var previousRow = triangle[rowIndex - 1],
        row = [],
        i, left, right, length;

    //if our row is the first row, the previous should be undefined
    //so we return an array containing only 1
    if (!previousRow) return [1];

    //we cache the limit to a variable to avoid property access overhead
    length = previousRow.length;

    //we run the loop from the first number to the cell after the last number
    for (i = 0; i <= length; i++) {

        //we start with the first number in the row and the one before that
        left = previousRow[i - 1];
        right = previousRow[i];

        //loose comparison is used since there are no zeroes in Pascal's triangle

        //if we start with the first number, the one before it should be undefined
        //thus we push the one at the right, which is our first number
        if (!left) {row.push(right);continue;}

        //if we end at the cell after the last number, that cell should be undefined
        //thus we push the one at the left, which is the last number in the row
        if (!right) {row.push(left);continue;}

        //if both conditions fail, this means left and right are both numbers
        //we add and push them to the current row
        row.push(left + right);
    }

    return row
}

for (var i = 0; i < depth; i++) {
    output.push(triangulate(output, i))
}

console.log(output.toString());

Looks long? Take a look at the comment-free version, pure code glory!

var depth = 6,
  output = [];

function triangulate(triangle, rowIndex) {

  var previousRow = triangle[rowIndex - 1],
    row = [],
    i, left, right, length;

  if (!previousRow) return [1];

  length = previousRow.length;

  for (i = 0; i <= length; i++) {

    left = previousRow[i - 1];
    right = previousRow[i];

    if (!left) {row.push(right);continue;}
    if (!right) {row.push(left);continue;}

    row.push(left + right)
  }
  return row;
}

for (var i = 0; i < depth; i++) {
  output.push(triangulate(output, i))
}

console.log(output.toString());

Try uglifying it, it's a billion times shorter!