の最適化非末尾再帰関数

Question

私は不可欠な操作次のように概説されているこの機能を持っている：

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>'; 
    } 
} 

私は私の人生のために、この機能を最適化する方法を見つけ出すことはできませんが。コールスタックが大きすぎると、PHPが爆発する恐れがあります。

この機能を最適化する方法はありますか？

Answer 1

このコードはテストされていないですが、私の頭の上から、反復関数は次のようなものになります。

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; 
} 

Answer 2

あなたがやっていることは効果的に木をたどることです。基本的には、ツリー内のすべての値を印刷するだけではありません。あなたはそれが大きすぎる特定の問題を経験しましたか？この木はどれくらい深くネストされていますか？

Answer 3

あなたが心配することは非常に疑わしいです。コールスタックがいっぱいになるほど深いdivを入れ子にしている場合、再帰の深さはあなたの心配の中で最も少なくなります。

Answer 4

ツリーの深度優先探索を行うために再帰を使用する必要はありません。それはちょうど本当に本当にうまく動作します。スタックを吹き飛ばすことが懸念される場合は、最後と現在の位置だけを保持するすべての要素に対して長いループを実行することができます。再帰は、深さ優先のトラバーサルを行うにはより簡単で（一般的に）より良い方法です。