Konvertieren rekursiver Funktion

Question

Ich habe eine rekursive Funktion hier, aber es verursacht Überlauf Fehler, so muss ich es in eine nicht-rekursive Funktion ändern. Jede Hilfe, wie man das macht, wird sehr geschätzt!

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

Im Allgemeinen, wenn Sie eine Baum-rekursive Funktion haben, die Ihren Stack überläuft, eine einfache Art und Weise in eine nicht-rekursive zu verwandeln (das verwendet stattdessen die Heap) ist im Wesentlichen Ihre eigenen Stapel zuordnen.

jedes Mal Ihre Funktion selbst mit einigen Argumenten aufrufen würde, stattdessen diese Argumente in eine struct stopfen, und schieben Sie diese struct in eine Arbeitswarteschlange (I „Warteschlange“ sagen, aber die tatsächliche Datenstruktur je ein std::stack oder std::queue sein könnte ob Sie Artikel in LIFO- oder FIFO-Reihenfolge bearbeiten möchten. Jetzt können Sie Ihre Funktion in einer iterativen Schleife aufrufen: Iterieren Sie diese Warteschlange, bis sie leer ist, setzen Sie alle Argumente ab und rufen Sie Ihre Funktion mit ihnen auf (die der Arbeitswarteschlange neue Elemente hinzufügen könnte).