Может ли кто-нибудь объяснить, как выполняются инструкции после завершения рекурсии?

Question

void ReversePrint(Node *head) 
{ 
    Node *sec=(Node *)malloc(sizeof(Node)); 
    sec->next=NULL; 
    sec->data=0; 
    if(head!=NULL) 
    { 
     ReversePrint(head->next); 
     Node *tmp=sec; 
     tmp->data=head->data; 
     cout<<tmp->data<<endl; 
     tmp=tmp->next; 
    } 
cout<<"hello"<<endl; 
} 

вход: 2 1 4 5

выход: - привет привет привет привет привет

Я не понимаю, как привет печатается перед последний элемент (первый элемент в этом случае, т.е. обратный порядок) связанного списка.

Answer 1

tmp и sec являются ненужными и просто вызывают утечку памяти каждый раз. Удалите их и использовать вместо:

cout << head->data << endl; 

Итак:

void ReversePrint(Node *node) 
{ 
    //cout << "("; 
    if (node != NULL) 
    { 
     ReversePrint(head->next); 
     cout << node->data << endl; 
    } 
    cout << "hello" << endl; 
    //cout << "hello" << ")" << endl; 
} 

Что было сделано не служит никакой цели, это выглядит как попытка повернуть вспять сам список, но это должно быть сделано по-другому, без распределение.

Answer 2

В принципе, вы вызываете ReversePrint() с "head = 2" -> "next = 1" -> "next = 4" -> "next = 5" -> "next = NULL". Только тогда наступает первый cout, печать привет. Затем программа восстанавливает стек вызовов (возвращается к узлу «5»), печатает , а затем привет. Затем снова повторяя (возвращаясь к узлу «4») ... и т.д.

Если вы хотите, чтобы избежать этого первого «привет» (а также принимая во внимание другие ответы), попробуйте следующее:

void ReversePrint(Node * node) 
{ 
    if(node == NULL) // to make sure the very first element of the list is not NULL 
     return; 

    if(node->next != NULL) 
     ReversePrint(node->next); 

    cout << node->data << endl; 
    cout << "hello" << endl; 
}