Pipers Pastete

Rekursion

Eine Funktion ist rekursiv, wenn sie sich selbst aufruft.

Ein wichtiger Unterschied zwischen einem Funktionsaufruf und einer Schleife besteht darin, dass ein Funktionsaufruf die Rücksprungadresse auf den Stack legt. Das bedeutet, dass eine rekursive Funktion meist mehr Stack-Speicher benötigt als eine entsprechende Schleife.

Deshalb kann eine Funktion, die sich immer wieder selbst aufruft, irgendwann den gesamten Stack-Speicher aufbrauchen. Das nennt man einen Stack Overflow.

Deshalb muss jede rekursive Funktion mindestens einen Basisfall haben. Das ist der Fall, in dem die Funktion zurückkehrt, ohne sich selbst aufzurufen. Jeder rekursive Aufruf muss irgendwann einen Basisfall erreichen.

Zum Beispiel lässt sich die Fakultätsfunktion n! = n * (n - 1) * ... * 1 rekursiv mit 1 als Basisfall definieren:

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

Beachte, dass factorial vor dem rekursiven Aufruf push rdi und danach pop rdi ausführen muss. Das liegt daran, dass es n noch braucht, wenn der rekursive Aufruf zurückkehrt, um n * (n-1)! zu berechnen.

Beachte außerdem, dass ein callee-saved Register dieses Problem nicht lösen würde.

Auch wenn eine rekursive Funktion ein möglicher Aufrufer ihrer selbst ist, ist sie selbst der Aufgerufene einer anderen Funktion. Das heißt, die Funktion muss auch callee-saved Register erhalten, bevor sie sie benutzt, und ihren Wert wiederherstellen, nachdem sie sie benutzt hat. Das geschieht meist mit einer push/pop-Sequenz, wie wir es in einem früheren Konzept gesehen haben.

Da jeder Frame einer rekursiven Funktion, mit Ausnahme des Basisfalls, ebenfalls ein Aufrufer ist, der seine eigenen lokalen Variablen erhalten muss, muss diese push/pop-Sequenz für jeden Frame wiederholt werden. Selbst wenn man die Variable direkt im Stack ablegt, ohne Register zu benutzen, würde das pro Frame trotzdem dieselben 8 Bytes kosten.

Das bedeutet, dass jeder rekursive Aufruf 8 Bytes für die von call auf den Stack gelegte Rücksprungadresse hinzufügt, plus 8 Bytes für jede lokale Variable, die gespeichert werden muss. Die Funktion fügt diese Bytes mit jedem Frame zum Stack hinzu, bis sie ihren Basisfall erreicht. Erst dann beginnt sie, sich in umgekehrter Reihenfolge abzubauen, wobei jeder rekursive Aufruf so viele pop benutzt wie nötig und danach ein ret.

Zum Beispiel würde factorial mit dem Argument 10 sich selbst neun Mal aufrufen, bevor es den Basisfall 1 erreicht. Zu diesem Zeitpunkt wären 144 Bytes benutzt worden, um für jeden vorherigen Frame n (8 Bytes) und die Rücksprungadresse (8 Bytes) zu speichern.

Endaufruf

In manchen Situationen erledigt eine Funktion nach dem Aufruf einer anderen und vor der Rückkehr keine weitere Arbeit mehr.

Betrachte zum Beispiel:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

Die Funktion triple_of_square:

• multipliziert das übergebene Argument (in rdi) mit sich selbst und erhält so sein Quadrat;
• danach ruft sie times_three auf, was das Dreifache des übergebenen Arguments zurückgibt.

Folglich gibt triple_of_square 3*x² zurück, wobei x das in rdi übergebene Argument ist.

Beachte, dass in triple_of_square nach dem Aufruf von times_three keine Arbeit mehr erledigt wird, die Funktion kehrt einfach zurück. In einer solchen Situation kann eine Funktion statt call ein jmp benutzen und die Ausführung an die aufgerufene Funktion übergeben:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

Das nennt man einen Endaufruf.

Der größte Vorteil eines Endaufrufs ist, dass die zusätzlichen Kosten von call entfallen. Ein call legt eine Rücksprungadresse auf den Stack, und damit die Kontrolle dorthin zurückkehrt, muss es ein passendes ret geben.

Ein Endaufruf überspringt beides: Es gibt keine Rücksprungadresse, die auf den Stack gelegt werden müsste, und kein zusätzliches ret, mit dem sie gepaart werden müsste, nur das eigene ret der aufgerufenen Funktion.

Endrekursion

Ein Endaufruf ist besonders nützlich für rekursive Funktionen, die sich selbst viele Male aufrufen können, bevor sie zurückkehren.

Allerdings lässt sich nicht jeder rekursive Aufruf direkt in einen Endaufruf übersetzen. Da ein jmp die Kontrolle an die aufgerufene Funktion übergibt, kann der Aufrufer nach dem Endaufruf keine weitere Arbeit mehr erledigen.

Zum Beispiel ist die frühere Funktion factorial nicht endrekursiv. Nach dem rekursiven Aufruf muss sie das Ergebnis noch mit dem aktuellen n multiplizieren, und zwar mit imul rax, rdi.

In solchen Situationen ist es manchmal möglich, einen Akkumulator zu benutzen, der Teilergebnisse sammelt und am Ende zurückgegeben wird. Zum Beispiel können wir einen factorial_helper definieren, der den größten Teil der Arbeit erledigt, und dann richtet factorial einen Akkumulator ein und übergibt die Kontrolle an factorial_helper:

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

Da nach dem rekursiven Aufruf keine Arbeit mehr erledigt wird, müssen wir rdi auch nicht mehr speichern. Es gibt kein call und kein push rdi, und daher fügt jede rekursive Iteration dem Stack 0 Bytes hinzu: Es wird kein zusätzlicher Stack-Speicher benutzt. Diese Version kann beliebig große n verarbeiten, ohne den Stack zum Überlaufen zu bringen. Sie ist sowohl effizienter als auch sicherer.

In manchen Fällen lässt sich durch eine Umsortierung der Funktionen sogar das jmp zum Helfer vermeiden. Zum Beispiel lassen sich factorial und triple_of_square so umschreiben:

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

Im obigen Ausschnitt geht die Ausführung von factorial direkt in factorial_helper über. Dasselbe passiert mit triple_of_square und times_three. In beiden Fällen läuft die Ausführung sequenziell weiter, und es scheint, als wäre die Endfunktion nur ein lokales Label innerhalb der „Hauptfunktion“.

In Wirklichkeit gibt es keinen wesentlichen Unterschied zwischen einem lokalen Label und einer Funktion. x86-64-Assembly behandelt keines von beiden besonders, sie sind einfach Adressen in einem Abschnitt mit ausführbarem Code, wie zum Beispiel section .text.

So kann man sich eine endrekursive Funktion im Wesentlichen genauso vorstellen wie eine Schleife, bei der der rekursive Aufruf zurück an den Anfang springt und der Basisfall die Bedingung ist, die die Schleife beendet.