Récursivité | AlgorithmeFacile

🔄 Notions de base : La Récursivité

Comprendre le principe d’auto-appel, la condition d’arrêt et la pile d’exécution.

📌 Définition

La récursivité est une méthode algorithmique qui consiste à appeler un sous-programme dans son propre corps. Un sous-programme récursif fait appel à lui-même jusqu’à ce qu’une condition d’arrêt soit vérifiée. À chaque appel, une nouvelle instance du module est empilée avec ses propres paramètres formels et variables locales.

1. Condition(s) d’arrêt :
Condition fondamentale permettant de stopper les appels récursifs et d’éviter une boucle infinie (dépassement de pile / Stack Overflow).

2. Appel(s) récursif(s) :
L’instruction où le module s’appelle lui-même en réduisant la taille du problème (ex: N-1, sous-chaîne, etc.).

📝 Remarque : itératif ou récursif ?

Sur le plan théorique, toute solution itérative peut être transformée en solution récursive, et réciproquement, toute fonction récursive dite « terminale » (c’est-à-dire dont l’appel récursif est la toute dernière instruction, sans aucun calcul après le retour de l’appel) peut être réécrite sous forme d’une boucle itérative équivalente, en général plus économe en mémoire (pas d’empilement d’appels).

En pratique, ce n’est pas toujours simple ni souhaitable :

Récursif ➔ Itératif : direct pour la récursivité terminale (ex : Mystere1, Mystere4 ci-dessous, la factorielle, la puissance…). Pour une récursivité non terminale (un calcul a lieu après l’appel récursif, comme Retourner A + Mystere1(A, B-1)), la traduction itérative demande souvent de gérer soi-même une pile explicite pour reproduire le comportement de la pile d’exécution.
Itératif ➔ Récursif : toujours possible en transformant les variables de boucle en paramètres de la fonction et la condition de boucle en condition d’arrêt.

Certains problèmes, en revanche, n’ont pas de solution itérative simple et sont naturellement (voire quasi exclusivement) traités par récursivité, en particulier lorsque la structure de données elle-même est récursive (arbres, listes chaînées) ou lorsque l’algorithme doit explorer plusieurs branches à chaque étape :

Les Tours de Hanoï (voir la simulation plus bas) : la formulation itérative existe mais est nettement moins naturelle et nécessite de gérer explicitement une pile de mouvements ; la version récursive découle directement de la définition du problème.
Le parcours d’arbres et de structures récursives (arbres binaires, dossiers/sous-dossiers, expressions imbriquées) : chaque nœud pointe vers d’autres sous-arbres de même nature, ce que la récursivité modélise directement.
Le backtracking (résolution de labyrinthes, du sudoku, des N-reines, génération de toutes les combinaisons/permutations) : il faut explorer puis « revenir en arrière », ce que la pile d’appels gère naturellement.
La fonction d’Ackermann (exercice 29 ci-dessous) : sa croissance et sa définition mathématique n’admettent pas d’équivalent itératif simple sans pile explicite très complexe.
Le tri fusion et le tri rapide : le principe « diviser pour régner » (diviser le tableau, trier chaque moitié, fusionner) est intrinsèquement récursif.

📐 Exemple 1 : Calcul de la Factorielle (N!)

-- Code de la solution --

🔤 Exemple 2 : Chaîne Palindrome (Python)

def palindrome(ch):
    if ch == "":
        return True
    elif ch[0] != ch[len(ch)-1]:
        return False
    else:
        return palindrome(ch[1 : len(ch)-1])

🎬 Simulation Pile d’Exécution : Fact(N)

N =

Pile d’exécution vide

💻 Exercices Interactifs : Exécution à la main & Simulations

Analysez les fonctions récursives suivantes (qui ne possèdent pas de variables locales). Donnez le résultat d’une exécution à la main, déduisez le rôle de chaque fonction, puis lancez la simulation pour visualiser la pile d’exécution.