Przyczyna instrukcji return w wywołaniu funkcji rekurencyjnej

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.

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).

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.