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.
$previous = array(1);
$next = array();
for($i=1; $i<=$rows_to_generate; $i++)
// the first element in each row is 1
$next = 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;
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.
There were a couple things that you could do with the original version that may have gotten hidden with the revised algorithm.
echo $storage[$i][$j]=get_elem($i,$j); // generate
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.
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.