Motivo dell'istruzione return in chiamata ricorsiva

13

Ho solo avuto un dubbio nella mia mente. La seguente subroutine (per cercare un elemento, in un elenco, ad esempio) ha un'istruzione return alla fine:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    return( search_list(l->next, x) );
}

Non riesco a ottenere il significato dell'istruzione di ritorno alla fine (per esempio, restituisci search_list (l- > next, x)). Sarebbe davvero utile se qualcuno potesse spiegare questo concetto, usando il modello di stack.

    
posta user1369975 17.06.2013 - 07:13
fonte

2 risposte

18

Un'istruzione return restituisce un valore al chiamante immediato del frame di chiamata della funzione corrente. Nel caso della ricorsione, questo chiamante immediato può essere un'altra chiamata di quella stessa funzione.

Nella maggior parte delle lingue, se non si utilizza il valore di ritorno di una funzione chiamata (in modo ricorsivo o meno), quel valore di ritorno viene scartato o si tratta di un errore diagnosticabile. Ci sono alcune lingue in cui il valore di ritorno dell'ultima chiamata di funzione viene automaticamente riutilizzato come valore di ritorno della chiamata di funzione corrente, ma non distinguono tra chiamate di funzioni normali e ricorsive.

Supponendo che i valori di ritorno non utilizzati vengano eliminati automaticamente, se hai scritto il codice in questo modo:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    search_list(l->next, x); // no return!
}

allora search_list restituirebbe solo un valore definito per una lista vuota (NULL) o se il primo elemento corrisponde al valore che stai cercando. Non appena la funzione passa alla chiamata ricorsiva, non si sa quale sarà il risultato, perché il risultato della chiamata ricorsiva viene scartato.

Inoltre, prometti di restituire un valore dalla tua funzione, ma hai un percorso (quello ricorsivo) in cui non specifichi quale valore restituire. A seconda della lingua che usi, questo di solito risulta in una diagnosi obbligatoria o in un comportamento indefinito (che significa abbreviazione: tutto può accadere e può cambiare in qualsiasi momento senza preavviso. la tua presentazione più importante). Ci sono alcune situazioni in cui il valore restituito mancante potrebbe sembrare funzionare, ma potrebbe cambiare al prossimo avvio del programma (con o senza ricompilazione).

    
risposta data 17.06.2013 - 09:57
fonte
1

Due cose; Restituire l'intera lista nel caso in cui trovi che la "x" che stai cercando non garantisce necessariamente l'utilizzo della ricorsione, ma a parte questo, considera quanto segue:

Supponiamo che tu stia cercando un valore di X="Dicembre" e che la tua lista sia il valore numerico dei mesi dell'anno, un puntatore al mese successivo e che gli elementi l- > nella lista siano il farro i nomi dei mesi. (Gennaio, febbraio, ..., dicembre). Hai bisogno dei tre ritorni per i possibili risultati. Il primo, return (NULL) è necessario se la lista non contiene la X che stai cercando. Il secondo, (return (l)) restituisce la lista, in questo caso, facendoti sapere che hai trovato la tua "x". L'ultimo è dove entra in gioco il modello di stack. Le chiamate successive alla funzione avrebbero aggiornato le variabili locali (in particolare, l- > item's) in questo modo:

1: l->item = January
   returns search_list(l->next, x)
2: l->item = February
   returns search_list(l->next, x)
3-11: March, April, May, June, July, August, September, October, November
   all return search_list(l->next, x)
12: l->item = December
  This matches the second if() and returns your list, letting you know you found your search item.
    
risposta data 17.06.2013 - 08:20
fonte

Leggi altre domande sui tag