Unterschied zwischen Schwanzrekursion und struktureller Rekursion

Gibt es einen Unterschied zwischen Strukturrekursion und Schwanzrekursion oder sind beide gleich? Ich sehe, dass in diesen beiden Rekursionen die rekursive Funktion für die Teilmenge der ursprünglichen Elemente aufgerufen wird.

1. Strukturelle Rekursion: Rekursive Aufrufe werden für strukturell kleinere Argumente durchgeführt.

2. Schwanzrekursion: Der rekursive Aufruf ist das Letzte, was passiert.

Es ist nicht erforderlich, dass die Schwanzrekursion für ein kleineres Argument aufgerufen wird. Tatsächlich sind Schwanzrekursionsfunktionen häufig so konzipiert, dass sie für immer eine Schleife bilden. Hier ist zum Beispiel eine triviale Schwanzrekursion (nicht sehr nützlich, aber es ist eine Schwanzrekursion):

def f(x):
   return f(x+1)

Wir müssen tatsächlich etwas vorsichtiger sein. Eine Funktion kann mehrere rekursive Aufrufe enthalten, und nicht alle müssen rekursiv sein:

def g(x):
  if x < 0:
    return 42             # no recursive call
  elif x < 20:
     return 2 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(x - 3)     # tail recursive

Man spricht von rekursiven Schwanzaufrufen . Eine Funktion, deren rekursive Aufrufe alle schwanzrekursiv sind, wird dann als rekursive Schwanzfunktion bezeichnet.

Die Schwanzrekursion ist ein sehr einfacher Fall der strukturellen Rekursion, bei der es sich bei der fraglichen Struktur um eine verknüpfte Liste handelt . In der Sprache, die Sie wahrscheinlich hauptsächlich verwenden, ist diese Liste wahrscheinlich nicht wörtlich im Code enthalten. Vielmehr handelt es sich um eine konzeptionelle "Liste von Aufrufen der Funktion", ein Konzept, das möglicherweise nicht so ausgedrückt werden kann, wie es in dieser Sprache geschrieben wurde. In Haskell (meiner Sprache) kann jeder schwanzrekursive Funktionsaufruf tatsächlich durch Sequenzierungsaktionen in einer Literalliste ersetzt werden, deren Elemente buchstäblich "Aufrufe einer Funktion" sind, aber dies ist wahrscheinlich eine funktionale Sprache.

Die strukturelle Rekursion ist eine Methode zum Bearbeiten eines Objekts, das als Verbund aus anderen (möglicherweise zusammengesetzten) Objekten definiert ist. Ein Binärbaum ist beispielsweise ein Objekt, das Verweise auf zwei Binärbäume enthält, oder ist leer (daher handelt es sich um ein rekursiv definiertes Objekt). Weniger selbstreferenziell lässt ein Paar (t1, t2), das zwei Werte einiger Typen t1 und t2 enthält, eine strukturelle Rekursion zu, obwohl t1 und t2 nicht auch Paare sein müssen. Diese Rekursion hat die Form

Aktion für das Paar = Kombination der Ergebnisse anderer Aktionen für jedes Element

das klingt nicht sehr tief.

Es ist häufig der Fall, dass eine strukturelle Rekursion nicht schwanzrekursiv sein kann , obwohl jede Art von Rekursion als Schwanzrekursion umgeschrieben werden kann (Beweis: Wenn Sie die ursprüngliche Rekursion ausführen, werden die Aktionen in einer bestimmten Reihenfolge ausgeführt, daher die Rekursion ist gleichbedeutend mit der Ausführung dieser bestimmten Abfolge von Aktionen, die, wie ich zuvor besprochen habe, eine Schwanzrekursion ist.

Entweder der Binärbaum oder das obige Paarbeispiel zeigen dies: Wenn Sie jedoch die rekursiven Aufrufe für die Unterobjekte anordnen, kann nur einer von ihnen die letzte Aktion sein. möglicherweise ist keiner von beiden, wenn ihre Ergebnisse auf irgendeine Weise kombiniert werden (z. B. Addition). Wie Andrej Bauer in seiner Antwort sagt, kann dies sogar mit nur einem rekursiven Aufruf geschehen, solange das Ergebnis geändert wird. Mit anderen Worten, für jeden Objekttyp außer denjenigen, die effektiv verknüpfte Listen sind (nur ein Unterobjekt ganz nach unten), ist strukturelle Rekursion keine Schwanzrekursion.