4
\$\begingroup\$

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);
}
\$\endgroup\$
2
  • \$\begingroup\$ 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]. \$\endgroup\$
    – mellamokb
    Apr 22 '13 at 14:16
  • \$\begingroup\$ 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. \$\endgroup\$
    – RobH
    Apr 22 '13 at 14:58
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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