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.

• Viral: great suggestions. can you explain this in detail? PHP does a lot of things implicitly that you can optimize better in languages that do them explicitly
• Brythan: @Viral As an example, note that you never set a size for your storage matrix. PHP implicitly sizes and resizes the array of arrays. However, we know the size in the beginning. There's no need to resize. We can allocate memory once at the beginning. This is also true of my $next and $previous arrays.

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)

• Viral: +1 for coding style suggestion, does variable name length affects the benchmark of code ?
• janos: It shouldn't affect