Perché una chiamata di ritorno ricorsiva esce dallo stack senza un'istruzione di reso esplicita?

Question

Mi è stato mostrato un programma di esempio per dimostrare la ricorsione che sembra non dovrebbe funzionare ma lo fa. La logica è abbastanza chiara, ma perché funziona anche quando la chiamata di funzione ricorsiva non viene restituita? Sembra che il comando return esca dallo stack anche se non è richiesto. È uno standard di linguaggio o una cosa gcc? L'ho visto con C e C++ compilato con gcc su Windows e Linux.

#include <iostream> 
#include <cstdlib> 

using namespace std; 

int isprime(int num, int i) 
{ 
    if (i == 1) { 
     return 1; 
    } 
    else { 
     if (num % i == 0) 
     return 0; 
     else 
     isprime(num, i-1); // should be returned 
    } 
} 


int main(int argc, char** argv) 
{ 
    int input = atoi(argv[1]); 
    cout << input << "\t" << isprime(input, input/2) << "\n"; 
} 

Answer 1

Cose del genere funzionano solo se accidentalmente il valore di ritorno si trova nel registro in cui il chiamante si aspetta. Funziona solo se questo viene realizzato dal compilatore come funzione ricorsiva. Tecnicamente è un comportamento non definito per utilizzare il valore restituito di una funzione che non ne fornisce uno.

Modifica: Nelle architetture moderne il valore di ritorno di una funzione per i valori per cui è possibile viene passato in un registro hardware specifico. Quando si chiama la funzione in modo ricorsivo, in basso in tutti i casi in cui il registro hardware è impostato sul valore previsto. Se per caso quando si apre dalla ricorsione che il registro hardware non viene mai modificato, si ottiene il valore corretto.

Tutto questo modello non funzionerebbe, se il valore di ritorno fosse posizionato in qualche posizione delle pile dei chiamanti (ricorsivi).

In ogni caso, tutto ciò dovrebbe essere acquisito da qualsiasi compilatore moderno e fornire un avviso. Se non lo fai non hai un buon compilatore, o stai usando le opzioni della linea di comando troppo difensive.

Speciale di capodanno: Nel mondo reale, un codice come questo (con return) non viene nemmeno realizzato come funzione ricorsiva. Con non troppo sforzo troverai una variante iterativa di quella funzione, e qualsiasi compilatore moderno decente dovrebbe essere in grado di trovarlo anche se chiedi l'ottimizzazione massima.

Answer 2

Non stai dimenticando una dichiarazione di reso? Per la normale ricorsione è necessario inserire un ritorno prima dello isprime(num,i-1);.

Immagino che anche questo dovrebbe dare un avviso di compilazione se si compila questo usando regole severe, perché la funzione deve sempre restituire un int, ora non lo fa (almeno se il compilatore non aggiusta questo).

Answer 3

Molto dipende da cosa intendi per "funziona"?

per provare a rispondere al punto principale della domanda, le funzioni restituiranno quando viene raggiunta la fine della funzione, indipendentemente dal fatto che venga soddisfatta o meno una dichiarazione di ritorno.

Mi aspetto di vedere gli avvisi del compilatore che indicano che i possibili percorsi di controllo potrebbero non restituire un valore, in C++ in ogni caso. Con conseguente comportamento indefinito, vedere questa domanda: not returning a value from a non-void returning function

Direi che questo esempio "funziona" come dopo un primo viene trovato e isPrime è tornato, quindi la funzione successiva lo stack è anche libero di tornare. Nulla dipende dal valore di ritorno di isPrime, quindi il programma eseguirà il backup dello stack e produrrà qualcosa.

... ma poiché il comportamento non è definito, è probabile che il valore effettivamente generato sia spazzatura. Se vedi 0 & 1 coerente con i primi come input, quindi wow.

Se pensi che funzioni, esaminerei i test più in generale con valori diversi.

Inoltre state costruendo con le impostazioni di "debug"? In tal caso, prova nuovamente con le impostazioni di debug, poiché a volte eseguono ulteriori operazioni per mantenere pulita la memoria non inizializzata.

Answer 4

posso spiegare esattamente ciò che accade:

La funzione viene richiamata, e recurses in se stesso fino a raggiungere la restituzione o modulo (ritorno 0) o alla fine di ricorsione (ritorno 1). A questo punto la funzione ritorna al chiamante, che è is_prime. Ma non c'è più codice nella funzione da eseguire, quindi ritorna immediatamente senza ulteriori azioni.

Tuttavia, si potrebbe facilmente interrompere questo, ad esempio, aggiungere printf("Done for %d, %d\n", num, i); dietro la chiamata di is_prime() [non deve essere presente nell'istruzione if]. O aggiungendo un oggetto C++ che è stato creato e distrutto all'ingresso/uscita della funzione, come un altro esempio.

Sei solo fortunato che funzioni. Ed è molto fragile e facile da rompere - compila con un compilatore diverso (o con diverse impostazioni di ottimizzazione, o una nuova versione del compilatore, o un milione di altre cose), e potrebbe anche rompersi.