Fonctions récursives : Factorielle et Fibonacci

1. La pensée récursive : cas de base et cas récursif

Un algorithme est dit récursif s'il résout un problème en se ramenant à la résolution d'un ou plusieurs sous-problèmes de même nature, mais de taille plus petite. Pour qu'une définition récursive soit valide, elle doit impérativement comporter deux éléments :

1. Un ou plusieurs cas de base : Ce sont des cas "triviaux" pour lesquels la solution est connue immédiatement, sans avoir besoin de faire un nouvel appel récursif. Le cas de base garantit la terminaison de l'algorithme.
2. Un cas récursif (ou général) : Il exprime la solution du problème en fonction de la solution d'un ou plusieurs sous-problèmes. L'étape récursive doit systématiquement "réduire la taille" du problème pour converger vers un cas de base.

L'exemple canonique est celui de la fonction factorielle, notée $n!$. Sa définition mathématique est intrinsèquement récursive :

Ici, $n=0$ est le cas de base. L'expression $n\times (n-1)!$ est le cas récursif.

Pour approfondir cette définition et voir comment elle se traduit en algorithme, je vous invite à regarder la vidéo suivante. Elle compare l'approche itérative, que vous connaissez certainement, à l'approche récursive.

2. Comment s'exécute une fonction récursive ? La pile d'appels

Comprendre la définition est une chose, mais visualiser l'exécution en est une autre. Lorsqu'une fonction f(n) appelle récursivement f(n-1), l'exécution de f(n) est suspendue et mise en attente. Un nouvel environnement est créé pour l'appel f(n-1). Ce mécanisme est géré par une structure de données fondamentale du système d'exécution : la pile d'appels (ou call stack).

Chaque appel de fonction "empile" un nouveau contexte (ses paramètres, ses variables locales, l'endroit où reprendre l'exécution). Lorsqu'une fonction se termine, son contexte est "dépilé" et la valeur de retour est transmise à la fonction appelante, qui peut alors reprendre son exécution.

La vidéo suivante illustre parfaitement ce mécanisme pour la fonction factorielle.

Pour visualiser cette séquence d'appels, on utilise un arbre d'appels. Pour la factorielle, cet "arbre" est en fait une simple branche linéaire.

En Python, la fonction s'écrirait ainsi :

def factorial(n: int) -> int:



    # Cas de base
    if n == 0:
        return 1



    # Cas récursif
    else:
        return n * factorial(n - 1)




# Exemple d'appel
print(factorial(4)) # Affiche 24

3. Une récursivité arborescente : la suite de Fibonacci

La récursivité n'est pas toujours linéaire. Considérons la suite de Fibonacci, définie par :

Ici, nous avons deux cas de base ($n=0$ et $n=1$) et un cas récursif qui fait deux appels à lui-même. L'arbre d'appels ne sera plus une ligne, mais bien un arbre binaire.

La vidéo suivante détaille la définition et le tracé de l'arbre d'appels pour Fibonacci.

Pour une visualisation encore plus claire et une explication très rigoureuse du lien entre l'arbre d'appels et la pile d'appels, la vidéo ci-dessous (en anglais) est une référence.

En Python, l'implémentation est une traduction directe de la définition mathématique :

def fibonacci(n: int) -> int:



    # Cas de base
    if n <= 1:
        return n



    # Cas récursif
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)




# Exemple d'appel
print(fibonacci(5)) # Affiche 5

4. Exercices : à vous de tracer

La meilleure manière de consolider votre compréhension est de tracer vous-même les arbres d'appels. Prenez une feuille de papier et un crayon.

Exercice 1 : factorial(4)

1. Dessinez le premier appel : un nœud étiqueté factorial(4).
2. Cet appel génère un appel à factorial(3). Dessinez un nœud pour factorial(3) sous le premier et reliez-les.
3. Continuez jusqu'à atteindre le cas de base factorial(0).
4. Maintenant, "remontez" l'arbre. Inscrivez la valeur de retour à côté de chaque nœud. factorial(0) retourne 1. factorial(1) reçoit 1 et calcule 1 * 1 = 1, qu'il retourne. Continuez jusqu'à la racine.

Exercice 2 : fibonacci(4)
Procédez de la même manière pour fibonacci(4). Vous verrez l'arbre se diviser en deux branches à chaque étape. Notez les valeurs de retour et calculez les sommes lors de la remontée.

• Que remarquez-vous concernant l'appel à fibonacci(2) ? Combien de fois est-il calculé ? Cette observation sera cruciale lorsque nous aborderons la programmation dynamique.

Pour aller plus loin et voir à quoi ressemblent ces arbres dans un contexte plus formel, vous pouvez consulter le document de cours suivant.

Conclusion

Cette leçon vous a introduit au paradigme de la récursivité, une pierre angulaire de l'informatique théorique et pratique.

Points clés à retenir :

• Une fonction récursive est définie par un cas de base (condition d'arrêt) et un cas récursif (appel à soi-même sur un problème plus petit).
• L'exécution est gérée par la pile d'appels : chaque appel est empilé, puis dépilé lorsque son résultat est calculé.
• L'arbre d'appels est une représentation visuelle de la séquence d'appels. Sa forme (linéaire, arborescente) dépend du nombre d'appels récursifs dans le corps de la fonction.
• Savoir tracer cet arbre est la première étape pour comprendre la complexité d'un algorithme récursif. Le nombre total de nœuds dans l'arbre est directement lié au volume de travail effectué.

Dans notre prochaine leçon, nous allons justement formaliser cette notion de "volume de travail". Maintenant que nous savons visualiser l'exécution d'un algorithme, nous allons apprendre le langage pour en mesurer l'efficacité : les notations asymptotiques O, Ω, et Θ. Cela nous permettra de comparer les algorithmes de manière rigoureuse.