再帰関数の変換

Question

ここで再帰関数がありますが、オーバーフローエラーが発生しているため、非再帰関数に変更する必要があります。どのようにそれを行うにはどんな助けも大歓迎です！一般的に

void MergeSort(struct node** headRef) 
{ 
    node* head = *headRef; 
    node* a; 
    node* b; 
    if ((head == NULL) || (head->next == NULL)) 
    { 
     return; 
    } 

    FrontBackSplit(head, &a, &b); 
    MergeSort(&a); 
    MergeSort(&b); 
    *headRef = SortedMerge(a, b); 
} 

Answer 1

あなたがスタックをオーバーフロー木再帰関数を持っている場合は、非再帰的1（代わりにヒープを使用していること）にそれを変換する簡単な方法は、本質的に、独自のスタックを割り当てることです。

あなたの関数は、いくつかの引数で自身を呼び出す代わりにstructにこれらの引数を詰め込むと、作業キューにstructことをプッシュする（私は「キュー」と言うが、実際のデータ構造が依存しstd::stackまたはstd::queue可能性がありますたびにあなたがアイテムをLIFOまたはFIFO注文で処理したいかどうか）。今度は反復ループで関数を呼び出すことができます：空になるまでそのキューを反復し、引数の各セットをポップアップしてそれらを使って関数を呼び出します（これにより、新しい項目が作業キューに追加される可能性があります）。