Grund für die return-Anweisung beim rekursiven Funktionsaufruf

14

Ich hatte nur einen Zweifel im Kopf. Die folgende Unterroutine (zum Beispiel zum Suchen eines Elements in einer Liste) hat am Ende eine return-Anweisung:

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

Ich kann die Bedeutung der return-Anweisung am Ende nicht abrufen (dh return search_list (l-> next, x)). Es wäre sehr hilfreich, wenn jemand dieses Konzept anhand eines Stack-Modells erläutern könnte.

user1369975
quelle
Wenn der erste Begriff der Liste nicht das Ergebnis ist, durchsuchen Sie den Rest der Liste . Dies ist, was der letzte returntut.
Giorgio
@ Giorgio, warum hätte nicht nur ein Funktionsaufruf gereicht, warum ist vorher eine Rückgabe nötig?
user1369975
7
Weil Sie den Wert zurückgeben müssen, der von der Funktion zurückgegeben wird
Esailija
7
Downvoter: Bitte beachten Sie, dass es je nach Hintergrund des OP überhaupt nicht offensichtlich ist, was dies returnbewirkt. Tatsächlich wird in funktionalen Sprachen (und einigen gemischten Sprachen wie Scala) return nicht benötigt : Der Wert der rekursiven Funktion ist der Wert ihres letzten Ausdrucks. Einfach search_list(l->next, x)ohne schreiben returnhätte in Scala geklappt! Die Bedeutung der returnAussage ist nur für Programmierer mit einem zwingenden Hintergrund offensichtlich.
Andres F.
OP: Ist Ihr Code-Snippet in C geschrieben?
Andres F.

Antworten:

19

Eine return-Anweisung übergibt einen Wert an den unmittelbaren Aufrufer des Aufrufrahmens der aktuellen Funktion. Im Falle einer Rekursion kann dieser unmittelbare Aufrufer ein weiterer Aufruf derselben Funktion sein.

Wenn Sie in den meisten Sprachen den Rückgabewert einer von Ihnen aufgerufenen Funktion nicht verwenden (rekursiv oder nicht), wird dieser Rückgabewert entweder verworfen oder es handelt sich um einen diagnostizierbaren Fehler. In einigen Sprachen wird der Rückgabewert des letzten Funktionsaufrufs automatisch als Rückgabewert des aktuellen Funktionsaufrufs wiederverwendet, es wird jedoch nicht zwischen normalen und rekursiven Funktionsaufrufen unterschieden.

Angenommen, nicht verwendete Rückgabewerte werden stillschweigend verworfen, wenn Sie den Code folgendermaßen geschrieben haben:

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

Dann wird search_listnur ein definierter Wert für eine leere Liste (NULL) zurückgegeben oder wenn das erste Element mit dem gesuchten Wert übereinstimmt. Sobald die Funktion in den rekursiven Aufruf eintritt, wissen Sie nicht, was das Ergebnis sein wird, da das Ergebnis des rekursiven Aufrufs verworfen wird.

Darüber hinaus versprechen Sie, einen Wert aus Ihrer Funktion zurückzugeben, aber Sie haben einen Pfad (den rekursiven), in dem Sie nicht angeben, welcher Wert zurückgegeben werden soll. Abhängig von der Sprache, die Sie verwenden, führt dies in der Regel entweder zu einer obligatorischen Diagnose oder zu undefiniertem Verhalten (was abgekürzt bedeutet: Es kann alles passieren und das kann sich jederzeit ohne Vorankündigung ändern. Machen Sie niemanden außer sich selbst haftbar, wenn es kaputt geht Ihre wichtigste Präsentation). In einigen Situationen scheint der fehlende Rückgabewert zu funktionieren, dies kann sich jedoch beim nächsten Ausführen des Programms ändern (mit oder ohne Neukompilierung).

Bart van Ingen Schenau
quelle
FWIW, Perl gibt das Ergebnis des letzten Ausdrucks automatisch zurück, was meiner Meinung nach bedeutet, dass der Rückgabewert wiederverwendet wird. Aber ich habe es seit Jahren nicht mehr angerührt, deshalb bin ich mir dessen nicht sicher.
Bobson
1

Zwei Dinge; Das Zurückgeben der gesamten Liste für den Fall, dass Sie das gesuchte "x" finden, rechtfertigt nicht unbedingt die Verwendung einer Rekursion. Beachten Sie jedoch Folgendes:

Angenommen, Sie suchen nach einem Wert von X = "Dezember", und Ihre Liste besteht aus dem numerischen Wert der Monate des Jahres, einem Zeiger auf den nächsten Monat, und die Einträge l-> in der Liste sind die buchstabierten Namen der Monate. (Januar, Februar, ..., Dezember). Sie benötigen die drei Rückgaben für die möglichen Ergebnisse. Der erste, return (NULL), wird benötigt, wenn die Liste das gesuchte X nicht enthält. Das zweite, (return (l)) gibt in diesem Fall die Liste zurück und teilt Ihnen mit, dass Sie Ihr "x" gefunden haben. Das letzte ist, wo das Stapelmodell ins Spiel kommt. Aufeinanderfolgende Aufrufe der Funktion hätten lokale Variablen (insbesondere l-> item's) wie folgt aktualisiert:

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
quelle
, danke für deine Illustration, aber nutze die letzte Rückkehr wirklich nicht
user1369975
Ohne die letzte Rückkehr kommt man nie an Schritt 1 vorbei.
Panhandel