Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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);
}
share|improve this question
Typically, recursive functions should not have side effects. This means you should not be mutating a variable getting passed down through the stack. It should be returned instead and combined with the current result in local variables with each iteration. Also you could I think make the code a little easier to understand by replacing some repeated expressions with variables, e.g.: triangle.length and triangle[triangle.length - 1]. – mellamokb Apr 22 at 14:16
I don't think this is the sort of problem that suits recursion - an iterative approach makes much more sense. You are doing an operation N times (the depth of the triangle) rather than breaking a problem down into smaller chunks. – RobH Apr 22 at 14:58

1 Answer

up vote 1 down vote

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.