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.