Przyczyna instrukcji return w wywołaniu funkcji rekurencyjnej

14

Po prostu miałem wątpliwości. Następujący podprogram (na przykład do wyszukiwania elementu na liście) ma na końcu instrukcję return:

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) );
}

Nie mogę uzyskać znaczenia instrukcji return na końcu (tj. Return search_list (l-> next, x)). Byłoby naprawdę pomocne, gdyby ktokolwiek mógł wyjaśnić tę koncepcję przy użyciu modelu stosu.

użytkownik1369975
źródło
Jeśli pierwszy termin na liście nie jest wynikiem, przeszukaj resztę listy . To właśnie returnrobi ostatni .
Giorgio
@ Giorgio, Dlaczego nie wystarczyłoby tylko wywołanie funkcji, dlaczego wcześniej potrzebny jest zwrot?
user1369975
7
Ponieważ musisz zwrócić wartość zwracaną przez funkcję
Esailija
7
Downvoters: proszę uświadomić sobie, że w zależności od tła PO, wcale nie jest oczywiste, co returnrobi. W rzeczywistości w językach funkcjonalnych (i niektórych mieszanych, takich jak Scala) return nie jest potrzebna : wartość funkcji rekurencyjnej jest wartością jej ostatniego wyrażenia. Po prostu pisanie search_list(l->next, x)bez returndziałałoby w Scali! Znaczenie tego returnstwierdzenia jest oczywiste tylko dla programistów z niezbędnym doświadczeniem.
Andres F.
OP: czy Twój fragment kodu jest napisany w C?
Andres F.

Odpowiedzi:

19

Instrukcja return przekazuje wartość z powrotem do bezpośredniego wywołującego ramki wywołania bieżącej funkcji. W przypadku rekurencji ten natychmiastowy obiekt wywołujący może być kolejnym wywołaniem tej samej funkcji.

W większości języków, jeśli nie używasz wartości zwracanej przez funkcję, którą wywołałeś (rekurencyjnie lub nie), albo ta wartość zwracana jest odrzucana, albo jest to błąd diagnozowalny. W niektórych językach wartość zwracana z ostatniego wywołania funkcji jest automatycznie ponownie wykorzystywana jako wartość zwracana z bieżącego wywołania funkcji, ale nie rozróżniają normalnych i rekurencyjnych wywołań funkcji.

Zakładając, że nieużywane wartości zwracane są dyskretnie odrzucane, jeśli kod został napisany w ten sposób:

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!
}

wtedy search_listzwróci tylko zdefiniowaną wartość dla pustej listy (NULL) lub jeśli pierwszy element pasuje do szukanej wartości. Gdy tylko funkcja przejdzie do wywołania rekurencyjnego, nie wiesz, jaki będzie wynik, ponieważ wynik wywołania rekurencyjnego zostanie odrzucony.

Ponadto obiecujesz zwrócić wartość z funkcji, ale masz ścieżkę (rekurencyjną), w której nie określasz, jaką wartość chcesz zwrócić. W zależności od używanego języka zwykle skutkuje to obowiązkową diagnostyką lub nieokreślonym zachowaniem (co jest skrótem: wszystko może się zdarzyć i może się zmienić w dowolnym momencie bez powiadomienia. Nie pociągaj nikogo oprócz siebie do odpowiedzialności, jeśli to popsuje twoja najważniejsza prezentacja). W niektórych sytuacjach może brakować zwracanej wartości, ale może się to zmienić przy następnym uruchomieniu programu (z rekompilacją lub bez).

Bart van Ingen Schenau
źródło
FWIW, Perl automatycznie zwraca wynik ostatniego wyrażenia, co moim zdaniem oznacza, że użyłoby ponownie wartości zwracanej. Ale nie dotknąłem tego od lat, więc nie jestem tego pewien.
Bobson,
1

Dwie rzeczy; Zwrócenie całej listy w przypadku znalezienia „x”, którego szukasz, niekoniecznie wymaga użycia rekurencji, ale poza tym rozważ następujące kwestie:

Załóżmy, że szukasz wartości X = „grudzień”, a twoja lista jest wartością liczbową miesięcy w roku, wskaźnikiem do następnego miesiąca, a pozycje l-> na liście są wypisanymi nazwami miesięcy. (Styczeń, luty, ..., grudzień). Potrzebujesz trzech zwrotów dla możliwych wyników. Pierwszy zwrot (NULL) jest potrzebny, jeśli lista nie zawiera szukanego X. Drugi (return (l)) zwraca listę, w tym przypadku, informując, że znalazłeś swoje „x”. Ostatni dotyczy modelu stosu. Kolejne wywołania funkcji zaktualizowałyby zmienne lokalne (konkretnie l-> itemy) w następujący sposób:

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.
panhandel
źródło
, dzięki za ilustrację, ale tak naprawdę nie korzystam z ostatniego zwrotu
użytkownik1369975,
Bez ostatniego powrotu nigdy nie przejdziesz kroku 1.
panhandel