Assemblersprache - Rekursion

Rekursion ist eine Technik, bei der sich eine Funktion selbst aufruft. Die Implementierung der Rekursion in Assembly erfordert eine ordnungsgemäße Stack-Frame-Verwaltung, wobei jeder Aufruf unabhängige Kopien von Parametern und lokalen Variablen besitzt.

Rekursionsprinzipien und Stack-Frames

Der Kern der Rekursion liegt darin, dassjeder Aufruf einen neuen Stack-Frame erstelltund den aktuellen Zustand auf dem Stack speichert.

Jeder rekursive Aufruf legt Parameter, die Rückspraddresse und lokale Variablen auf dem Stack ab. Wenn die Rekursion endet, werden die Stack-Frames Schicht für Schicht abgefragt (gepoppt), und jede Schicht erhält das Ergebnis ihres Unteraufrufs und schließt ihre Berechnung ab.

Rekursions-Grundlagen	Beschreibung	Assembly-Implementierung
Abbruchbedingung	Endlose Rekursion verhindern	Bedingte Prüfung + je/jg Sprung
Rekursiver Aufruf	Funktion ruft sich selbst auf	call Anweisung
Zustandsspeicherung	Unabhängiger Zustand für jeden Aufruf	Stack-Frame (push ebp; mov ebp, esp)
Parameterübergabe	Jedes Mal andere Parameter	Parameter auf den Stack pushen

Obwohl die Rekursion den Code elegant macht, hat jeder Aufruf in Assembly einen erheblichen Stack-Overhead. Eine übermäßige Rekursionstiefe kann zu einem Stacküberlauf führen. Für leistungssensitive Szenarien sollten Sie erwägen, die Rekursion als Schleife umzuschreiben.

Rekursive Fakultätsimplementierung

Beispiel

; Dateipfad: factorial.asm
; Rekursive Berechnung der Fakultät: n! = n * (n-1)!

section .data
n dd 5 ; Berechne 5!
result dd 0
output_msg db 'Fakultätsergebnis: '
output_len equ $ - output_msg
newline db 0xA

section .bss
result_str resb 12

section .text
global _start

_start:
; Rufe factorial(5) auf
push dword [n] ; Parameter n pushen
call factorial
add esp, 4 ; Parameter bereinigen
; eax = 120 (5!)

mov [result], eax

; Ergebnis ausgeben
mov eax, 4
mov ebx, 1
mov ecx, output_msg
mov edx, output_len
int 0x80

; Einfache numerische Ausgabe (nur für einstellige Demos)
mov eax, [result]
; Hier vereinfacht
mov ebx, eax
mov eax, 1
int 0x80

; Prozedur: factorial(n)
; Eingabe: [ebp+8] = n
; Ausgabe: eax = n!
factorial:
push ebp ; Alten Stack-Frame sichern
mov ebp, esp ; Neuen Stack-Frame einrichten

mov eax, [ebp + 8] ; Parameter n abrufen
cmp eax, 1 ; n <= 1 ?
jg recurse ; n > 1, Rekursion fortsetzen

; Abbruchbedingung: n <= 1, 1 zurückgeben
mov eax, 1
jmp factorial_end

recurse:
; Aktuelles n sichern (das Register wird durch den rekursiven Aufruf zerstört)
push eax ; n sichern

; Rekursiver Aufruf von factorial(n-1)
dec eax ; n - 1
push eax ; Argument: n-1
call factorial ; Rekursiver Aufruf
add esp, 4 ; Parameter bereinigen

; n wiederherstellen
pop ebx ; ebx = n

; eax = n * factorial(n-1)
mul ebx ; edx:eax = eax * ebx
; Für kleineres n ist edx 0 und das Ergebnis befindet sich vollständig in eax

factorial_end:
pop ebp ; Alten Stack-Frame wiederherstellen
ret

Der vollständige Aufruf-Stack und Rückgabeprozess für die rekursive Berechnung von factorial(5):

Das Folgende ist der textuelle Aufrufprozess:

factorial(5)
  -> 5 * factorial(4)
       -> 4 * factorial(3)
            -> 3 * factorial(2)
                 -> 2 * factorial(1)
                      -> 1  (终止条件)
                 <- 1 * 2 = 2
            <- 2 * 3 = 6
       <- 6 * 4 = 24
  <- 24 * 5 = 120

Rekursive Fibonacci-Implementierung

Beispiel

; Dateipfad: fibonacci.asm
; Rekursive Berechnung der Fibonacci-Folge: fib(n) = fib(n-1) + fib(n-2)

section .data
n dd 10 ; Berechne fib(10)

section .text
global _start

_start:
; Rufe fib(10) auf
push dword [n]
call fibonacci
add esp, 4
; eax = fib(10) = 55

mov ebx, eax ; Exit-Code = 55
mov eax, 1
int 0x80

; Prozedur: fibonacci(n)
; Eingabe: [ebp+8] = n
; Ausgabe: eax = fib(n)
fibonacci:
push ebp
mov ebp, esp

mov eax, [ebp + 8] ; Parameter n abrufen

; Abbruchbedingung: n zurückgeben, wenn n <= 1
cmp eax, 1
jg fib_recurse ; n > 1, Rekursion erforderlich
; n <= 1: fib(0)=0, fib(1)=1
jmp fib_end

fib_recurse:
; ★ Hinweis: Die Rekursion hat zwei Zweige, daher muss der Stack sorgfältig verwaltet werden
push ebx ; ebx speichern (wird zur Speicherung des Zwischenergebnisses verwendet)

; fib(n-1) berechnen
mov eax, [ebp + 8]
dec eax ; n - 1
push eax
call fibonacci
add esp, 4
mov ebx, eax ; ebx = fib(n-1) (Ergebnis speichern!)

; fib(n-2) berechnen
mov eax, [ebp + 8]
sub eax, 2 ; n - 2
push eax
call fibonacci
add esp, 4
; eax = fib(n-2)

; eax = fib(n-1) + fib(n-2)
add eax, ebx ; eax = fib(n-2) + fib(n-1)

pop ebx ; ebx wiederherstellen

fib_end:
pop ebp
ret

Die rekursive Version von Fibonacci beinhaltet viele doppelte Berechnungen. fib(10) ruft fib(9) und fib(8) auf, und fib(8) wird zweimal aufgerufen... was zu einer Zeitkomplexität von O(2^n) führt. In der echten Praxis wird empfohlen, die iterative Schleifenversion zu verwenden.

Iterative Fibonacci-Version (Vergleich)

Beispiel

; Dateipfad: fibonacci_iter.asm
; Iterative Version: effizienter, kein Rekursions-Overhead

section .data
n dd 10

section .text
global _start

_start:
mov ecx, [n] ; ecx = n
dec ecx ; n-1 Mal Schleife durchlaufen (beginnend beim 2. Term)

mov eax, 0 ; fib(0) = 0
mov ebx, 1 ; fib(1) = 1

cmp ecx, 0
jle fib_done ; n <= 1, direkt zurückkehren

fib_loop:
mov edx, ebx ; Das alte fib(n-1) speichern
add ebx, eax ; ebx = fib(n-1) + fib(n-2)
mov eax, edx ; fib(n-2) aktualisieren
loop fib_loop

fib_done:
; Für n=10 schließlich ebx = 55
mov eax, 1
mov ebx, ebx ; Rückgabewert = fib(n)
int 0x80

Vergleich zwischen Rekursion und Iteration

Merkmal	Rekursion	Iteration
Codegröße	Kürzer, klare Logik	Länger, aber gute Leistung
Stack-Nutzung	Jeder Aufruf belegt einen Stack-Frame; kann bei großer Tiefe überlaufen	Fester, kleiner Speicherbedarf
Leistung	Hat Aufruf-/Rückkehr-Overhead (call/ret)	Kein Funktionsaufruf-Overhead
Lesbarkeit	Intuitiv für Probleme mit vollständiger Induktion	Schleifenzustand muss manuell verwaltet werden
Anwendbare Szenarien	Baumtraversierung, Divide-and-Conquer-Algorithmen, vollständige Induktion	Einfache Wiederholung, leistungssensitive Szenarien

In der Assembly verbraucht jeder rekursive Aufruf Stack-Speicher. Die Standard-Stackgröße unter Linux beträgt etwa 8 MB, und eine Rekursion mit einer Tiefe von 100000 kann einen Stack-Überlauf verursachen. Wann man Rekursion einsetzen sollte: wenn die Rekursionstiefe des Problems kontrollierbar ist (wie bei einer balancierten Baumtiefe O(log n)) und die rekursive Logik viel klarer ist als die Iteration.

Weitere Erweiterungen