Pascal’s triangle for an interview in PHP

I saw that one of the interview questions could be building a pascal triangle.
Is there anything wrong with this particular solution I came up with?

function pascal_r($r){

   $local = array();

   if($r == 1){
       return array(array(1));
   } else {
       $previous = pascal_r($r - 1);

       array_push($local, 1);

           for($i = 0; $i < $r - 2 && $r > 2; $i++){
               array_push($local, $previous[$r-2][$i] + $previous[$r-2][$i + 1]);
           }

       array_push($local, 1);
   }

   array_push($previous, $local);

   return $previous;

}

print_r(pascal_r(100));

In regards to the comments: Yes, this is a good place for this so long as it works as is and you are asking about the code and not the algorithm. If you are asking about the algorithm this should have stayed on programmers.SE. If you are asking if this will work, then you should test it first, then if you can’t find a solution you should post this to SO. Now, assuming this works and you’re not asking about the algorithm, here are my thoughts:

A number of these points may be nitpicking, but the interviewers are likely to nitpick as well since they have so little code to review to determine how good you are. First example of this are your variable and function names, which could stand to be a bit more descriptive. I can guess what “r” might be, but spelling it out wouldn’t hurt, especially if that variable might get lost in layers of code. It makes your code “self-documenting”, this means less actual documentation and easier future integration.

Unless you have to add a number of elements on to an array at the same time, don’t use array_push(). There is no need to call a function to do something that can be done without one. This is also explicitly explained on the PHP documentation for this function should you need further proof.

$local[] = 1;//good

array_push( $local,
    1,
    2,
    //etc...
);//also good

array_push( $local, 1 );//bad

Watch your indentation. That for loop is needlessly indented. Needless whitespace and indentation add “weight” to your documents. Not much at any one time, but a weight that can build up steadily, especially if you are of the faction that uses spaces instead of tabs. This isn’t ever likely to cause any real world difficulties, except maybe slightly larger file sizes, but again, I’m nitpicking.

Something else you are going to get tagged on is all of these magic numbers. Where are these 1’s and 2’s coming from? If those numbers mean something, then you should create constants or variables to define it. Constants if immutable, variables if mutable. If, as in your first return statement you are merely returning the value of $r, as it appears, then you can just typecast it.

if( $r == 1 ) {
    return array( ( array ) $r );
}

Instead of doing the same operation, $r - 2, over and over again, set the value to a variable and use that instead. Its overhead may be slight, and again a nitpick, but it still adds up if done enough. Besides, it makes for much more legible code.

$r2 = $r - 2;//horrible name, don't use this
for( $i = 0; $i < $r2 && $r > 2; $i++ ) {

This next suggestion is similar to one I’ve already given. Watch your indentation. You have an if/else statement when you could really get away with just an if statement. Since it has an early return, you can drop the else statement, this removes one layer of indentation across six lines of code. In larger systems this could easily add up to quite a bit more and is easily one of the easiest, most visual, refactoring you can do.

The last bit of advice would be to use var_dump() over print_r(). While this may be a matter of preference, I find the type output beneficial, especially in cases where you could somehow get an empty array or FALSE value.

EDIT

Interesting coincidence here, but I’m taking a course on Coursera (Functional Programming in Scala), and one of the things we were required to do was find the value of a given coordinate on a pascal triangle. This assignment reminded me of this post so I thought I’d revisit it, but I wanted to wait until the deadline had been reached before posting this. Below is the code I used to functionally find the value.

• Note: I’m using spoilers to give you a chance to work it out. Try and do these yourself before peeking.

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

• Note: I stressed functional, but there are other ways of doing this. I’m merely keeping with my assignment’s guidelines.
• Note: I know I’m violating some of my own advice. The instructions I was given in my assignment stressed not to use variables, so I’m not.

So, given we can now find a value at any given coordinate, we should easily be able to use this to print a pascal triangle too. All we need is to determine how big we want our triangle to be and we can loop for it. I’m going to use 10, but you can change that amount to any value you want and it will still work. Again, no peeking!

    for( $i = 0; $i < 10; $i++ ) {
        for( $j = 0; $j <= $i; $j++ ) {
            echo pascal( $j, $i ) . ' ';
        }
        echo '<br />';
    }

There you have it. Not only have you printed a pascal triangle, but you’ve also created a function that can be reused to serve a better purpose, namely finding a coordinate value.

Is there anything wrong with this particular solution I came up with?

As mseancole points out, your answer does not highlight your ability to write readable code.

I am going to add one thing and suggest an alternate solution.

Needs a Comment

A function like this should have a comment at the top of it. It should describe what your function does. In this case I would also add in your comment that this function is unlikely to work for large triangles!

Why won’t it work?

Computations of this sort can run into fatal limits:

• Memory usage is too high (default configuration is 128MB). This is consumed by approximately 1340 levels.
• Execution Time

If you use xdebug you would also have:

• Nesting level too great (default configuration is 100)

One way to avoid deep nesting is to use an iterative solution rather than a recursive one. To me, the iterative solution is easier to understand here because each pascal number is the addition of the previous level’s elements that are to the left and right of the number.

/**
 * Get a pascal triangle of the specified depth.
 *
 * Large triangles require a lot of memory, be sure to set the memory limits
 * appropriately for the size of triangles you need to allocate.
 *
 * @param  int   The depth of the triangle to generate.
 * @return int[] The pascal triangle.
 */
function get_pascal_triangle($depth)
{
    $triangle = array();

    for ($level = 0; $level < $depth; $level++)
    {
        $prevLevel = $level - 1;

        for ($pos = 0; $pos < $level + 1; $pos++)
        {
            $triangle[$level][$pos] =
                isset($triangle[$prevLevel][$pos - 1],
                      $triangle[$prevLevel][$pos]) ?
                $triangle[$prevLevel][$pos - 1] + $triangle[$prevLevel][$pos] :
                1;
        }
    }

    return $triangle;
}