Récursion
Une fonction est récursive lorsqu'elle s'appelle elle-même.
Une différence clé entre un appel de fonction et une boucle est que l'appel d'une fonction empile l'adresse de retour sur la pile.
Cela signifie qu'une fonction récursive demande généralement plus d'espace de pile qu'une boucle équivalente.
Par conséquent, une fonction qui s'appelle sans cesse peut finir par épuiser tout l'espace de pile.
C'est ce qu'on appelle un débordement de pile.
C'est pourquoi toute fonction récursive doit avoir au moins un cas de base, c'est-à-dire une situation où la fonction renvoie une valeur sans s'appeler elle-même.
Tout appel récursif doit finir par atteindre un cas de base.
Par exemple, la fonction factorielle n! = n * (n - 1) * ... * 1 peut être définie de manière récursive avec 1 comme cas de base :
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
Note qu'il faut faire push rdi avant la récursion et pop rdi après.
En effet, elle a encore besoin de n une fois l'appel récursif terminé pour calculer n * (n-1)!.
Note aussi qu'utiliser un registre sauvegardé par l'appelé ne résoudrait pas ce problème.
Bien qu'une fonction récursive soit un appelant potentiel d'elle-même, elle est elle-même appelée par une autre fonction.
Cela signifie que la fonction doit aussi préserver les registres sauvegardés par l'appelé avant de les utiliser, et restaurer leur valeur après usage.
C'est généralement fait avec une séquence push/pop, comme nous l'avons vu dans un concept précédent.
Comme chaque cadre d'une fonction récursive, à l'exception du cas de base, est aussi un appelant qui doit préserver ses propres variables locales, cette séquence push/pop doit être répétée pour chaque cadre.
Même stocker la variable directement dans la pile, sans utiliser de registres, coûterait toujours les mêmes 8 octets par cadre.
Cela signifie que chaque appel récursif ajoute 8 octets à la pile pour l'adresse de retour empilée par call, plus 8 octets pour chaque variable locale qu'il doit sauvegarder.
La fonction continuera d'ajouter ces octets à la pile à chaque cadre jusqu'à ce qu'elle atteigne son cas de base.
Ce n'est qu'alors qu'elle commence à se dérouler dans l'ordre inverse, chaque appel récursif utilisant autant de pop que nécessaire puis un ret.
Par exemple, si factorial était appelée avec l'argument 10, elle s'appellerait elle-même neuf fois avant d'atteindre le cas de base 1.
À ce moment-là, 144 octets auraient été utilisés pour stocker le n (8 octets) et l'adresse de retour (8 octets) pour chaque cadre précédent.
Appel terminal
Dans certaines situations, une fonction n'effectue plus aucun travail après avoir appelé une autre fonction et avant de renvoyer.
Prenons par exemple :
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
call times_three
ret
La fonction triple_of_square :
- multiplie l'argument passé (dans
rdi) par lui-même, obtenant son carré ;
- puis elle appelle
times_three, qui renvoie trois multiplié par l'argument passé.
En conséquence, triple_of_square renvoie 3*x², où x est son argument, passé dans rdi.
Note qu'aucun travail n'est effectué dans triple_of_square après l'appel à times_three, la fonction renvoie simplement.
Dans une situation comme celle-ci, au lieu d'utiliser call, une fonction peut utiliser jmp et transférer l'exécution à la fonction appelée :
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
jmp times_three
C'est ce qu'on appelle un appel terminal.
Le principal avantage d'un appel terminal est d'éviter le coût supplémentaire de call.
Un call empile une adresse de retour sur la pile, et pour que le contrôle revienne à ce point, il doit y avoir un ret correspondant.
Un appel terminal saute les deux : il n'y a pas d'adresse de retour à empiler, et pas de ret supplémentaire à faire correspondre, juste le ret propre à la fonction appelée.
Récursion terminale
Un appel terminal est particulièrement utile pour les fonctions récursives qui peuvent s'appeler elles-mêmes de nombreuses fois avant de renvoyer.
Cependant, tout appel récursif ne peut pas être directement traduit en appel terminal.
Comme un jmp transfère le contrôle à la fonction appelée, l'appelant ne peut plus effectuer de travail après l'appel terminal.
Par exemple, la fonction factorial précédente n'est pas récursive terminale.
Après l'appel récursif, elle doit encore multiplier le résultat par le n courant, en utilisant imul rax, rdi.
Dans des situations comme celle-ci, il est parfois possible d'utiliser un accumulateur qui collectera les calculs partiels et sera renvoyé à la fin.
Par exemple, nous pouvons définir un factorial_helper qui effectue la majeure partie du travail, puis factorial met en place un accumulateur et transfère le contrôle à 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
Comme plus aucun travail n'est effectué après l'appel récursif, nous n'avons plus besoin de sauvegarder rdi.
Il n'y a ni call ni push rdi, et donc chaque itération récursive ajoute 0 octet à la pile : aucun espace de pile supplémentaire n'est utilisé.
Cette version peut gérer des n arbitrairement grands sans déborder de la pile.
Elle est à la fois plus efficace et plus sûre.
Dans certains cas, en manipulant l'ordre des fonctions, même le jmp vers la fonction auxiliaire peut être évité.
Par exemple, factorial et triple_of_square peuvent être réécrites de cette façon :
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
Dans l'extrait ci-dessus, l'exécution de factorial se poursuit dans factorial_helper.
Il en va de même pour triple_of_square et times_three.
Dans les deux cas, l'exécution continue séquentiellement et il semble que la fonction terminale ne soit qu'une étiquette locale à l'intérieur de la fonction « principale ».
En réalité, il n'y a pas de différence essentielle entre une étiquette locale et une fonction.
L'assembleur x86-64 ne leur accorde aucun traitement particulier, ce ne sont que des adresses dans une section de code exécutable, comme section .text.
De cette façon, une fonction récursive terminale peut être considérée comme essentiellement équivalente à une boucle où l'appel récursif revient au début, et où le cas de base est la condition qui met fin à la boucle.
Exercice d'apprentissage
