Pascal's triangle in PHP

Question

Are there any optimization suggestions?

<?php
# Pascal's Triangle using Recursion.
$rows_to_generate = 15; // Define number of rows you want to generate.
$storage = array();
function get_elem($row,$pos)    // generate element having number of row and number of position.
{
    global $storage;

    if(isset($storage[$row][$pos]))
    {
        return $storage[$row][$pos];
    }

    if($row==1 and $pos==1) // for first row.
    {
        return 1;
    }
    else if($pos==0)    // for left most row element that doesn't exist.
    {
        return 0;
    }
    else if($pos>$row)  // for right most row element that doesn't exist.
    {
        return 0;
    }
    return get_elem($row-1,$pos-1)+get_elem($row-1,$pos);   // Recursion
}
?>
<pre>
<?php
for($i=1;$i<=$rows_to_generate;$i++)
{
    for($j=1;$j<=$i;$j++)
    {
        echo $storage[$i][$j]=get_elem($i,$j);  // generate
        if($i!=$j)
        {
            echo ' ';
        }
    }
    echo '<br>';
}
?>
</pre>

Answer 1

Are there any optimization suggestions?

Certainly. This is not a good candidate for recursion. A more efficient method is to build the triangle. Calculate the first row. Output it. Use it to calculate the second row. Then you can forget the first row. You'll never need it again.

<pre>
<?php
$previous = array(1);
$next = array();
for($i=1; $i<=$rows_to_generate; $i++)
{
    // the first element in each row is 1
    $next[0] = 1;

    for($j=1; $j<$i; $j++)
    {
        $next[$j] = $previous[$j] + $previous[$j-1];
    }

    echo implode(' ', $next) . '<br>';

    $previous = $next;
    $next = array();

    // there is one more element in the new row than the old
    $previous[] = 0;
}
?>
</pre>

This is rather similar in structure to your original code. Mostly the same two for loops. However, the original code makes 358 calls to your recursive function even with memoization. Changing the base condition to return 1 instead of 0 as @janos suggests saves 56 calls, so 302 total. This code does only 165 assignments and 15 of those are the trivial "first element in each row is 1" assignments. Another 45 are for updating the row arrays between loop iterations.

Original Algorithm

There were a couple things that you could do with the original version that may have gotten hidden with the revised algorithm.

for($j=1;$j<=$i;$j++)
{
    echo $storage[$i][$j]=get_elem($i,$j);  // generate
    if($i!=$j)
    {
        echo ' ';
    }
}

You can avoid the internal if by saying

for ($j = 1; $j < $i; $j++)
{
    $storage[$i][$j] = get_elem($i,$j);
    echo $storage[$i][$j] . ' ';
}
echo $storage[$i][$j] = get_elem($i,$j);

This trades a mostly duplicated line of code for getting rid of an if statement that is only not true once in the loop iterations.

Note that my version uses implode to handle the spaces. My quick check suggests that implode takes about the same time as this method.

Language

PHP is not an ideal language for processing mathematical operations and arrays. PHP does a lot of things implicitly that you can optimize better in languages that do them explicitly.

Answer 2

These conditions can be simplified:

if($row==1 and $pos==1) // for first row.
{
    return 1;
}
else if($pos==0)    // for left most row element that doesn't exist.
{
    return 0;
}
else if($pos>$row)  // for right most row element that doesn't exist.
{
    return 0;
}

To this:

if ($pos == 1 or $row == $pos)
{
    return 1;
}

Coding style

The expressions are too packed. It would be better to add more spaces:

• around operators
• after semicolons
• after commas in parameter lists
• before opening ( of if conditions and for loops

So instead of this:

for($i=1;$i<=$rows_to_generate;$i++)
{
    for($j=1;$j<=$i;$j++)
    {
        echo $storage[$i][$j]=get_elem($i,$j);  // generate
        if($i!=$j)

This is easier to read:

for ($i = 1; $i <= $rows_to_generate; $i++)
{
    for ($j = 1; $j <= $i; $j++)
    {
        echo $storage[$i][$j] = get_elem($i, $j);  // generate
        if ($i != $j)