Optimizing a non-tail-recursive function.

Question

I have this function whose essential operations are outlined as follows:

function render($index) {
    foreach($things[$index] as $key => $data) {
        echo '<div>';
        /* irrelevant operations */
        if(isset($data['id'])) {
            echo '<div class="wrap">';
            render($things[$data['id']]);
            echo '</div>';
        }
        echo '</div>';
    }
}

I can not for the life of me figure out how to optimize this function; I fear that PHP implode if the call stack gets too big.

Is there any way to optimize this function?

Answer 1

What you're doing is effectively traversing a tree. Basically, this is no worse than just printing all the values in a tree. Have you experienced any specific troubles with it getting too large? How deeply nested is this tree?

Answer 2

It's highly doubtful that you have to worry. If you're nesting divs deep enough that the call stack fills up, recursion depth is the least of your worries.

Answer 3

You don't NEED to use recursion to do a depth-first traversal of your tree; it just happens to work really really well. If blowing your stack is a concern, you could just run a long loop on all your elements holding just the last and current positions. Recursion is a simpler and (generally) better way to perform the depth-first traversal though.

Answer 4

This code is untested, but from the top of my head, the iterative function should look something like this:

function render($index){
 $stack = array();
 array_push($index);

 $pre = '';
 $post = '';

 while(!empty($stack)){
  $idx = array_pop($stack);

  foreach($things[$idx] as $key => $value){
   $pre .= '<1>';
   $spost = '';

   if(isset($data['id'])){
    $pre .= '<2 class="wrap">';
    $spost .= '</2>';

    $stack[] = $things[$data['id']];
   }

   $spost .= '</1>';
   $post .= $spost;
  }
 }

 return $pre . $post;
}