Langage d'assemblage - Récursivité

La récursion est une technique dans laquelle une fonction s'appelle elle-même. Implémenter la récursion en assembleur nécessite une gestion appropriée des cadres de pile, chaque appel ayant des copies indépendantes des paramètres et des variables locales.

Principes de la récursion et cadres de pile

Le cœur de la récursion réside dansle fait que chaque appel crée un nouveau cadre de pile, en sauvegardant l'état actuel sur la pile.

Chaque appel récursif empile les paramètres, l'adresse de retour et les variables locales sur la pile. Lorsque la récursion se termine, les cadres de pile sont dépilés couche par couche, et chaque couche reçoit le résultat de son sous-appel et termine son calcul.

L'essentiel de la récursion	Description	Implémentation en assembleur
Condition de terminaison	Éviter la récursion infinie	Vérification conditionnelle + saut je/jg
Appel récursif	La fonction s'appelle elle-même	instruction call
Sauvegarde de l'état	État indépendant pour chaque appel	Cadre de pile (push ebp; mov ebp, esp)
Passage de paramètres	Paramètres différents à chaque fois	empiler les paramètres sur la pile

Bien que la récursivité rende le code élégant, chaque appel en assembleur a un coût de pile considérable. Une profondeur de récursion excessive peut provoquer un débordement de pile. Pour les scénarios sensibles aux performances, envisagez de réécrire la récursion sous forme de boucle.

Implémentation récursive de la factorielle

Exemple

; Chemin du fichier : factorial.asm
; Calculer récursivement la factorielle : n! = n * (n-1)!

section .data
n dd 5 ; Calculer 5!
result dd 0
output_msg db 'Résultat de la factorielle : '
output_len equ $ - output_msg
newline db 0xA

section .bss
result_str resb 12

section .text
global _start

_start:
; Appel de factorial(5)
push dword [n] ; Empiler le paramètre n
call factorial
add esp, 4 ; Nettoyer les paramètres
; eax = 120 (5!)

mov [result], eax

; Sortie du résultat
mov eax, 4
mov ebx, 1
mov ecx, output_msg
mov edx, output_len
int 0x80

; Sortie numérique simple (pour démo à un seul chiffre uniquement)
mov eax, [result]
; Simplifié ici
mov ebx, eax
mov eax, 1
int 0x80

; Procédure : factorial(n)
; Entrée : [ebp+8] = n
; Sortie : eax = n!
factorial:
push ebp ; Sauvegarder l'ancien cadre de pile
mov ebp, esp ; Mettre en place le nouveau cadre de pile

mov eax, [ebp + 8] ; Récupérer le paramètre n
cmp eax, 1 ; n <= 1 ?
jg recurse ; n > 1, continuer la récursion

; Condition d'arrêt : n <= 1, retourner 1
mov eax, 1
jmp factorial_end

recurse:
; Sauvegarder le n actuel (le registre sera détruit par l'appel récursif)
push eax ; Sauvegarder n

; Appeler récursivement factorial(n-1)
dec eax ; n - 1
push eax ; Argument : n-1
call factorial ; Appel récursif
add esp, 4 ; Nettoyer les paramètres

; Restaurer n
pop ebx ; ebx = n

; eax = n * factorial(n-1)
mul ebx ; edx:eax = eax * ebx
; Pour les petites valeurs de n, edx vaut 0, et le résultat est entièrement dans eax

factorial_end:
pop ebp ; Restaurer l'ancien cadre de pile
ret

La pile d'appels complète et le processus de retour pour le calcul récursif de factorial(5) :

Voici le processus d'appel sous forme textuelle :

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

Implémentation récursive de Fibonacci

Exemple

; Chemin du fichier : fibonacci.asm
; Calculer récursivement la suite de Fibonacci : fib(n) = fib(n-1) + fib(n-2)

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

section .text
global _start

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

mov ebx, eax ; Code de sortie = 55
mov eax, 1
int 0x80

; Procédure : fibonacci(n)
; Entrée : [ebp+8] = n
; Sortie : eax = fib(n)
fibonacci:
push ebp
mov ebp, esp

mov eax, [ebp + 8] ; Récupérer le paramètre n

; Condition d'arrêt : renvoyer n lorsque n <= 1
cmp eax, 1
jg fib_recurse ; n > 1, récursion nécessaire
; n <= 1：fib(0)=0, fib(1)=1
jmp fib_end

fib_recurse:
; Remarque : la récursion a deux branches, donc la pile doit être gérée avec soin
push ebx ; Sauvegarder ebx (il sera utilisé pour stocker le résultat)

; Calculer fib(n-1)
mov eax, [ebp + 8]
dec eax ; n - 1
push eax
call fibonacci
add esp, 4
mov ebx, eax ; ebx = fib(n-1) (sauvegarder le résultat !)

; Calculer fib(n-2)
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 = eax + ebx

pop ebx ; Restaurer ebx

fib_end:
pop ebp
ret

La version récursive de Fibonacci comporte beaucoup de calculs en double. fib(10) appelle fib(9) et fib(8), et fib(8) est appelé deux fois... ce qui entraîne une complexité temporelle de O(2^n). En ingénierie réelle, il est recommandé d'utiliser la version itérative avec boucle.

Version itérative de Fibonacci (comparaison)

Exemple

; Chemin du fichier : fibonacci_iter.asm
; Version itérative : plus efficace, sans surcoût de récursion

section .data
n dd 10

section .text
global _start

_start:
mov ecx, [n] ; ecx = n
dec ecx ; Boucler n-1 fois (en partant du 2e terme)

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

cmp ecx, 0
jle fib_done ; n <= 1, retourner directement

fib_loop:
mov edx, ebx ; Sauvegarder l'ancien fib(n-1)
add ebx, eax ; ebx = fib(n-1) + fib(n-2)
mov eax, edx ; Mettre à jour fib(n-2)
loop fib_loop

fib_done:
; Pour n=10, finalement ebx = 55
mov eax, 1
mov ebx, ebx ; Valeur de retour = fib(n)
int 0x80

Comparaison récursion vs itération

Fonctionnalité	Récursion	Itération
Taille du code	Plus court, logique claire	Plus long, mais bonnes performances
Utilisation de la pile	Chaque appel occupe un cadre de pile ; peut déborder lorsque la profondeur est grande	Quantité d'espace fixe et réduite
Performance	A un surcoût d'appel/retour	Aucun surcoût d'appel de fonction
Lisibilité	Intuitif pour les problèmes d'induction mathématique	Nécessite de maintenir manuellement l'état de la boucle
Scénarios applicables	Parcours d'arbre, algorithmes de type diviser pour régner, induction mathématique	Répétition simple, scénarios sensibles aux performances

En assembleur, chaque appel récursif consomme de l'espace de pile. La taille de pile par défaut sous Linux est d'environ 8MB, et une récursion d'une profondeur de 100000 peut provoquer un débordement de pile. Comment juger quand utiliser la récursion : lorsque la profondeur de récursion du problème est contrôlable (comme la profondeur d'un arbre équilibré O(log n)), et que la logique récursive est beaucoup plus claire que l'itération.

Autres extensions