Principes de la récursion en programmation

📋 Plan du Cours

1. Programmation récursive Python
2. Fonction factorielle récursive
3. Appels récursifs et condition d'arrêt
4. Arbre d'appels récursifs
5. Complexité exponentielle Fibonacci
6. Mémoïsation Fibonacci
7. Suite récurrente ordre 1
8. Calcul itératif suite récurrente
9. Calcul récursif suite récurrente
10. Suite récurrente ordre 2
11. Exponentiation naïve
12. Exponentiation rapide récursive

📖 1. Programmation récursive Python

🔑 Notions clés & Définitions

• Fonction récursive : Fonction qui s'appelle elle-même dans son corps d'exécution, permettant de résoudre un problème en le décomposant en sous-problèmes plus simples. Selon Généralités (source), une fonction f est dite récursive si son exécution peut provoquer un ou plusieurs appels à elle-même.

• Appel principal : Premier appel à une fonction récursive lancé dans le programme, qui initie la chaîne d'appels récursifs. Il se distingue des appels récursifs qui sont provoqués par l'exécution de la fonction elle-même (Généralités).

• Appels récursifs : Occurrences où la fonction s'appelle elle-même durant son exécution, en suivant la relation de récurrence. Ces appels sont responsables de la décomposition du problème et de la propagation vers la condition d'arrêt (Généralités).