Лист за преговор: 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).

• Structure d'une fonction récursive : Organisation du code comprenant une ou plusieurs conditions d'arrêt (pour éviter la récursion infinie) et une ou plusieurs opérations incluant des appels récursifs, permettant de suivre la relation de récurrence. Selon Généralités, cette structure est toujours composée d'une condition d'arrêt et d'un ou plusieurs appels récursifs.

• Support en Python : Python supporte la programmation récursive, ce qui n'est pas systématiquement le cas dans tous les langages de programmation. Cela permet d'implémenter directement des relations de récurrence mathématique dans le code (Introduction).

📝 Points essentiels

• La programmation récursive s'inspire directement des relations de récurrence en mathématiques, permettant de décomposer un problème en sous-problèmes plus simples, puis de combiner leurs solutions pour obtenir la résultat final.

• La structure d'une fonction récursive comporte toujours deux éléments fondamentaux : une condition d'arrêt qui termine la récursion pour éviter une boucle infinie, et une étape de calcul qui inclut un ou plusieurs appels récursifs suivant la relation de récurrence.

• La différence principale entre approche itérative et récursive pour un même calcul réside dans la manière dont le problème est résolu : l'approche itérative utilise une boucle pour répéter le processus, tandis que la récursive utilise des appels successifs à la fonction elle-même.

• La récursivité permet une écriture plus intuitive et proche de la formulation mathématique, mais peut entraîner une consommation importante de mémoire (pile d'appels) et une complexité exponentielle si mal optimisée, comme dans le cas de la suite de Fibonacci naïve.

• En Python, la gestion des appels récursifs est facilitée par le support du langage, mais la profondeur maximale de récursion doit être surveillée pour éviter des erreurs de dépassement de pile (voir Généralités).

💡 À retenir

La programmation récursive en Python repose sur la définition d'une fonction qui s'appelle elle-même selon une relation de récurrence, structurée par une condition d'arrêt. Elle offre une rédaction intuitive pour certains algorithmes, mais nécessite une gestion prudente de la profondeur d'appel pour éviter les erreurs de dépassement de pile.

📖 2. Fonction factorielle récursive

🔑 Notions clés & Définitions

• Fonction récursive : Une fonction qui, lors de son exécution, peut provoquer un ou plusieurs appels à elle-même. Elle se caractérise par une condition d'arrêt et une relation de récurrence (voir section 1.1).
• Condition d'arrêt spécifique pour la factorielle : La valeur de la factorielle est définie par 0! = 1, ce qui sert de condition d'arrêt dans la fonction récursive.
• Relation de récurrence de la factorielle : La factorielle d’un entier n, notée n!, peut être exprimée par n! = n × (n−1)! pour n ≥ 1, avec 0! = 1 comme base (voir section 1.1).
• Implémentation en code Python : La fonction fact_rec(n) utilise la relation de récurrence et la condition d'arrêt pour calculer la factorielle récursivement :

def fact_rec(n):
    if n == 0:
        return 1
    else:
        return n * fact_rec(n - 1)

• Appel récursif : La fonction fact_rec s'appelle elle-même avec l'argument n−1, permettant de réduire le problème jusqu'à la condition d'arrêt (voir section 1.1).

📖 3. Appels récursifs et condition d'arrêt

🔑 Notions clés & Définitions

• Condition d'arrêt : Critère permettant de stopper la récursion pour éviter une boucle infinie. Elle correspond à une situation où la fonction ne s'appelle plus elle-même, généralement basée sur une valeur de l'argument ou une condition spécifique (ex : n==0 dans la factorielle).
  Source : AUTEUR (date) : "Une (ou plusieurs) condition d’arrêt, c’est l’équivalent de l’initialisation pour une récurrence."

• Appel récursif : Invocation de la même fonction à l’intérieur de sa propre définition, permettant de décomposer un problème en sous-problèmes plus simples. Il constitue le cœur de la programmation récursive, en répétant le processus jusqu’à la condition d’arrêt.
  Source : AUTEUR (date) : "Une fonction (ou procédure) f est dite récursive si son exécution peut provoquer un ou plusieurs appels de f elle-même."

• Rôle des appels récursifs dans la définition : Ils permettent d’implémenter une relation de récurrence en décomposant le problème en versions plus petites, jusqu’à atteindre la condition d’arrêt. La valeur de retour de chaque appel est utilisée pour construire la solution finale.
  Source : AUTEUR (date) : "La relation de récurrence n! = n × (n−1)! traduit en code récursif, repose sur un appel récursif."

• Exemple de la factorielle récursive : La fonction fact_rec(n) illustre la récursion avec une condition d’arrêt (n==0) et un appel récursif (n*fact_rec(n-1)). La condition d’arrêt évite une récursion infinie en arrêtant la décomposition lorsque n atteint 0.
  Source : AUTEUR (date) : "La ligne 2-3 correspond à la condition d’arrêt, qui traduit la condition initiale 0! = 1."

• Importance de la condition d'arrêt : Elle est essentielle pour prévenir la récursion infinie, qui entraînerait une erreur de dépassement de la capacité de la pile d’appels (RecursionError). Elle garantit que la fonction finit par retourner une valeur, assurant la terminaison de l’algorithme.
  Source : AUTEUR (date) : "L’importance de la condition d’arrêt pour éviter récursion infinie."

📝 Points essentiels

• La programmation récursive repose sur deux éléments fondamentaux : la condition d’arrêt et les appels récursifs. La condition d’arrêt doit être définie avec précision pour garantir la terminaison de la fonction.
• La relation de récurrence est traduite en code par un appel récursif, qui décompose le problème en sous-problèmes plus simples, jusqu’à atteindre la condition d’arrêt.
• La structure d’une fonction récursive comporte toujours une ou plusieurs conditions d’arrêt, qui jouent un rôle crucial pour éviter une récursion infinie. Par exemple, dans la fonction fact_rec(n), la condition if n==0 est la condition d’arrêt.
• La visualisation par arbre d’appels permet de comprendre comment la récursion se déploie et de vérifier que la condition d’arrêt est bien atteinte, évitant ainsi une explosion du nombre d’appels.
• La complexité de la récursion peut être exponentielle si la condition d’arrêt n’est pas bien définie ou si la structure des appels est mal conçue. La mémoïsation est une technique pour réduire cette complexité en stockant les résultats intermédiaires.

💡 À retenir

La condition d’arrêt est le pivot qui garantit la fin de la récursion, tandis que les appels récursifs permettent de décomposer un problème en sous-problèmes plus simples, en suivant une relation de récurrence. Leur bonne définition assure la terminaison et l’efficacité de l’algorithme récursif.

📖 4. Arbre d'appels récursifs

🔑 Notions clés & Définitions

• Représentation sous forme d’arbre d’appels : Visualisation graphique de la succession des appels récursifs d’une fonction, où chaque nœud représente un appel et chaque branche une transition vers un appel subséquent. Elle permet d’analyser la structure et la complexité de la récursion (exemple : arbre pour fact_rec(4)).
• Appels récursifs successifs : Série d’appels à une fonction qui se produisent de manière linéaire ou arborescente, suivant la relation de récurrence, jusqu’à atteindre la condition d’arrêt. Par exemple, dans fact_rec(4), chaque appel réduit l’argument de 1 jusqu’à 0.
• Propagation des valeurs de retour : Processus par lequel, après l’atteinte de la condition d’arrêt, les valeurs calculées remontent dans l’arbre d’appels pour être combinées selon la relation de récurrence, comme la multiplication dans fact_rec ou l’addition dans Fibonacci.
• Arbre d’appels complexe : Structure d’arbre où certains appels récursifs apparaissent plusieurs fois, notamment dans la suite de Fibonacci, illustrant la redondance et l’inefficacité du calcul naïf (exemple : F(4) avec F(1) et F(2) répétés).
• Appels multiples et redondants : Situation où un même appel récursif est effectué plusieurs fois indépendamment, entraînant une explosion du nombre d’appels et une inefficacité, comme dans l’arbre de Fibonacci naïf. La mémoïsation permet de réduire cette redondance en stockant les résultats intermédiaires.

📝 Points essentiels

• La représentation en arbre d’appels est un outil fondamental pour comprendre la dynamique des fonctions récursives, notamment leur profondeur et leur complexité. Elle montre comment chaque appel engendre de nouveaux appels, formant une structure arborescente.
• Dans le cas de fact_rec(4), l’arbre est une chaîne linéaire de 5 appels, chacun réduisant l’argument de 1, jusqu’à la condition d’arrêt (n=0). La valeur de retour remonte alors en remontant l’arbre, en multipliant successivement.
• Pour la suite de Fibonacci, l’arbre d’appels est plus complexe : chaque appel à F(n) génère deux appels à F(n-1) et F(n-2), ce qui entraîne une croissance exponentielle du nombre d’appels. La redondance est manifeste, avec plusieurs appels à F(1) et F(0).
• La visualisation de ces arbres permet d’identifier la source de l’inefficacité dans la récursivité naïve, notamment par la répétition d’appels identiques. La mémoïsation est une solution pour optimiser cette structure en stockant les résultats déjà calculés, évitant ainsi les recalculs inutiles.
• La taille de la pile d’appels, liée à la profondeur de l’arbre, limite la récursivité en pratique, et la complexité en espace est proportionnelle à la profondeur de l’arbre (exemple : linéaire pour fact_rec, exponentielle pour Fibonacci naïf).

💡 À retenir

L’arbre d’appels récursifs est un outil essentiel pour analyser la structure, la complexité et l’efficacité d’un algorithme récursif, mettant en évidence la redondance des calculs et la nécessité d’optimisations comme la mémoïsation.

📖 5. Complexité exponentielle Fibonacci

🔑 Notions clés & Définitions

• Complexité exponentielle (voir section 1.4) : croissance du nombre d’appels récursifs ou du temps de calcul qui augmente de manière exponentielle en fonction de la taille de l’entrée n, notamment dans le cas de la fonction naïve de Fibonacci.
• Croissance exponentielle du nombre d'appels récursifs (voir section 1.4) : phénomène où le nombre d’appels récursifs effectués par une fonction, comme celle de Fibonacci naïve, double ou augmente de façon exponentielle avec n, entraînant une explosion du coût calculatoire.
• Complexité temporelle cachée (voir section 1.4) : coût en temps de calcul qui n’est pas immédiatement apparent, notamment dans la récursivité naïve, où le nombre d’appels redondants entraîne une croissance exponentielle du temps de traitement.
• Limites machine (voir section 1.4) : contraintes liées à la capacité mémoire ou à la profondeur maximale de la pile d’appels, qui empêchent l’exécution de fonctions récursives exponentielles pour de grandes valeurs de n, comme illustré par l’erreur "RecursionError".
• Approche récursive naïve de Fibonacci (voir section 1.4) : méthode récursive directe basée sur la relation $f(n) = f(n-1) + f(n-2)$, qui génère un arbre d’appels avec une croissance exponentielle du nombre d’appels, rendant l’algorithme inefficace pour de grandes valeurs de n.
• Comparaison avec approche itérative (voir section 1.4) : l’approche itérative de Fibonacci, utilisant une boucle, a une complexité en temps linéaire, contrairement à la récursive naïve, qui est exponentielle, ce qui explique la différence de performance significative.

📝 Points essentiels

• La fonction naïve de Fibonacci, définie par la relation $f(n) = f(n-1) + f(n-2)$, entraîne une croissance exponentielle du nombre d’appels récursifs, illustrée par l’arbre d’appels où certains sous-calculs sont répétés plusieurs fois.
• La croissance exponentielle du nombre d’appels récursifs implique que le temps de calcul augmente rapidement avec n, dépassant souvent la capacité de traitement des machines pour des valeurs modérées (exemple : $n=50$ provoque un plantage).
• La complexité temporelle cachée dans cette récursivité naïve est due à la redondance des calculs, ce qui rend l’algorithme inefficace en pratique.
• La comparaison entre approche récursive naïve et approche itérative montre que la première est beaucoup plus lente, avec une croissance exponentielle, alors que la seconde est linéaire, ce qui la rend exploitable pour des grandes valeurs de n.
• La limite de la pile d’appels, imposée par la capacité mémoire, peut également empêcher l’exécution de la récursion naïve pour de grandes valeurs, illustrant la nécessité d’optimiser ou de changer d’approche.

💡 À retenir

La croissance exponentielle du nombre d’appels récursifs dans la méthode naïve de Fibonacci rend cette approche inefficace en pratique, soulignant l’importance d’utiliser des techniques comme la mémoïsation ou l’approche itérative pour éviter cette explosion du coût calculatoire.

📖 6. Mémoïsation Fibonacci

🔑 Notions clés & Définitions

• Mémoïsation : technique consistant à stocker les résultats intermédiaires d’un calcul récursif pour éviter de les recalculer plusieurs fois, réduisant ainsi la complexité temporelle (voir section 1.4).
• Stockage des résultats intermédiaires : enregistrement des valeurs calculées lors de l’exécution d’un algorithme récursif afin de les réutiliser dans les appels suivants, ce qui limite le nombre d’appels récursifs (voir section 1.4).
• Application à la suite de Fibonacci : utilisation de la mémoïsation pour stocker les termes successifs de la suite de Fibonacci, permettant de réduire la croissance exponentielle du nombre d’appels récursifs (voir section 1.4).
• Amélioration de la complexité temporelle : grâce à la mémoïsation, la complexité passe d’exponentielle à linéaire en évitant la répétition des calculs (voir section 1.4).
• Réduction du nombre d’appels récursifs : en stockant les résultats, la mémoïsation limite le nombre d’appels à un nombre proportionnel à n, évitant la croissance exponentielle (voir section 1.4).

📝 Points essentiels

La mémoïsation est une méthode efficace pour optimiser les algorithmes récursifs en évitant de recalculer plusieurs fois les mêmes valeurs, ce qui est particulièrement pertinent dans le cas de la suite de Fibonacci. La suite de Fibonacci naïve, implémentée récursivement, génère un arbre d’appels avec une croissance exponentielle, ce qui rend le calcul impraticable pour de grandes valeurs de n. En stockant chaque terme calculé dans une structure de données (par exemple, un couple (un, un+1)), la mémoïsation permet de réduire le nombre d’appels récursifs à un ordre linéaire, améliorant significativement la performance (voir section 1.4).
L’approche avec mémoïsation conserve la simplicité de la récursivité tout en évitant ses principaux inconvénients liés à la complexité exponentielle. La fonction u_memo(f, u0, u1, n) illustre cette technique en stockant le couple de Fibonacci successif, permettant de répondre instantanément pour de grandes valeurs (voir section 2.2.C).

💡 À retenir

La mémoïsation transforme un algorithme récursif exponentiel en un algorithme linéaire en stockant et réutilisant les résultats intermédiaires, ce qui optimise considérablement la performance tout en conservant la simplicité de la récursion.

📖 7. Suite récurrente ordre 1

🔑 Notions clés & Définitions

• Suite récurrente d’ordre 1 : Suite de nombres définie par une relation de récurrence du type $u_{n+1} = f(u_n)$, où $f : R \to R$. La suite est entièrement déterminée par un terme initial $u_0$ et la fonction $f$ (voir section 2.1).
• Calcul du n-ième terme par approche itérative : Méthode consistant à appliquer la relation de récurrence successivement à partir de $u_0$ jusqu’à atteindre $u_n$, en utilisant une boucle pour effectuer ces calculs (voir section 2.1.A).
• Calcul du n-ième terme par approche récursive : Méthode utilisant la définition de la suite pour calculer $u_n$ en appelant récursivement la fonction $u_{n-1}$, en suivant la relation $u_{n+1} = f(u_n)$ et en utilisant une condition d’arrêt (voir section 2.1.B).
• Complexité temporelle entre approche itérative et récursive : Les deux méthodes ont une complexité en ordre de $n$ en termes de nombre d’opérations, mais la récursion implique une utilisation supplémentaire de la pile d’appels, ce qui peut entraîner une surcharge mémoire (voir section 2.1).
• Fonction $u_{it}$ et $u_{rec}$ pour suites d’ordre 1 : Fonctions illustrant respectivement l’approche itérative et récursive pour calculer le n-ième terme d’une suite récurrente d’ordre 1, avec leur structure respective.
  • $u_{it}(f, u_0, n)$ : utilise une boucle pour appliquer $f$ successivement $n$ fois (voir section 2.1.A).
  • $u_{rec}(f, u_0, n)$ : utilise la récursion pour appliquer $f$ en appelant $u_{rec}$ pour $n-1$ (voir section 2.1.B).

📝 Points essentiels

• La suite récurrente d’ordre 1 est entièrement caractérisée par $u_0$ et la fonction $f$, avec la relation $u_{n+1} = f(u_n)$. La suite doit être définie sur un intervalle $I$ stable par $f$.
• La méthode itérative calcule $u_n$ en effectuant $n$ itérations, ce qui est direct et efficace en termes de complexité temporelle, mais nécessite de stocker une seule variable $u$ à chaque étape.
• La méthode récursive, basée sur la relation $u_{n} = f(u_{n-1})$, effectue également $n$ appels récursifs, mais utilise la pile d’appels, ce qui peut poser des limites en mémoire (voir section 1.5).
• La complexité temporelle des deux approches est en ordre de $n$, mais la récursion peut entraîner une surcharge mémoire et un risque de dépassement de la limite de récursion (voir section 1.5).
• La fonction $u_{it}$ et $u_{rec}$ illustrent ces deux méthodes : $u_{it}$ avec boucle, $u_{rec}$ avec récursion, permettant de comparer leur efficacité et leur simplicité (voir section 2.1).

💡 À retenir

La suite récurrente d’ordre 1 peut être calculée efficacement par approche itérative ou récursive, ces deux méthodes ayant une complexité temporelle similaire, mais la récursion impliquant une surcharge mémoire qui limite son utilisation pratique.

📖 8. Calcul itératif suite récurrente

🔑 Notions clés & Définitions

• Calcul itératif du n-ième terme d'une suite récurrente d'ordre 1 : Méthode consistant à déterminer le terme $u_n$ en utilisant une boucle pour appliquer successivement la fonction $f$ à partir du terme initial $u_0$, jusqu'à atteindre le terme désiré.
• Utilisation d'une boucle pour appliquer la fonction f successivement : Processus où une structure répétitive (boucle) exécute plusieurs fois une opération $u = f(u)$, permettant d'obtenir le terme $u_n$ sans recours à la récursivité.
• Avantage en termes de complexité spatiale par rapport à la récursivité : La méthode itérative nécessite un espace mémoire constant, car elle ne stocke qu'une seule variable $u$, contrairement à la récursivité qui utilise une pile d'appels proportionnelle à $n$.
• Exemple de code Python pour calcul itératif de la suite :

def u_it(f, u0, n):
    u = u0
    for _ in range(n):
        u = f(u)
    return u

• Calcul de la liste des n+1 premiers termes par approche itérative : Construction progressive d'une liste contenant tous les termes de la suite jusqu'à $u_n$, en utilisant une boucle pour appliquer $f$ et stocker chaque résultat dans une liste.

📝 Points essentiels

• La méthode itérative repose sur une boucle qui répète l'application de $f$ à partir du terme initial $u_0$. Elle effectue ainsi $n$ opérations pour obtenir $u_n$.
• Elle est particulièrement efficace en termes de complexité spatiale, car elle ne nécessite que l'espace pour stocker une variable $u$, contrairement à la récursivité qui doit maintenir une pile d'appels dont la taille est proportionnelle à $n$.
• La simplicité de cette approche facilite la compréhension et l'implémentation, notamment dans des contextes où la profondeur de récursion est limitée ou coûteuse.
• La construction de la liste des termes permet de suivre l'évolution de la suite, utile pour analyser ou visualiser le comportement de la suite.
• La méthode est applicable à tout type de suite récurrente d'ordre 1 définie par $u_{n+1} = f(u_n)$, avec $u_0$ initial donné.

💡 À retenir

L'approche itérative, utilisant une boucle pour appliquer successivement $f$, est une méthode efficace et simple pour calculer le n-ième terme d'une suite récurrente d'ordre 1, avec un avantage notable en termes de complexité spatiale par rapport à la récursivité.

📖 9. Calcul récursif suite récurrente

🔑 Notions clés & Définitions

• Calcul récursif du n-ième terme d'une suite récurrente d'ordre 1 : Méthode consistant à déterminer un terme $u_n$ en utilisant la relation de récurrence $u_{n+1} = f(u_n)$ et une condition d'arrêt, généralement $u_0$. La fonction s'appelle elle-même pour calculer $u_{n-1}$, puis remonte la chaîne pour obtenir $u_n$.

• Structure récursive avec condition d'arrêt pour n=0 : Organisation d'une fonction récursive où la récursion s'arrête lorsque l'argument $n$ atteint 0, renvoyant la valeur initiale $u_0$. La condition d'arrêt évite la récursion infinie et sert de base pour la récurrence.

• Construction récursive de la liste des termes de la suite : Technique consistant à générer la liste complète $[u_0, u_1, ..., u_n]$ en appelant la fonction récursive pour $n-1$, puis en ajoutant le terme $u_n$, permettant de visualiser et exploiter la relation de récurrence dans un contexte itératif ou récursif.

• Comparaison des complexités spatiales et temporelles avec l'itératif : Analyse qui montre que, pour une suite récurrente d'ordre 1, l'approche récursive nécessite un nombre d'appels proportionnel à $n$ (complexité linéaire en espace et temps), comparable à l'approche itérative, mais avec une consommation mémoire plus importante en raison de la pile d'appels.

• Exemple de code Python pour calcul récursif de la suite : Implémentation concrète utilisant la relation $u_{n+1} = f(u_n)$ avec une condition d'arrêt pour $n=0$, illustrant la méthode récursive pour obtenir le terme $u_n$. Par exemple :

def u_rec(f, u0, n):
    if n == 0:
        return u0
    else:
        return f(u_rec(f, u0, n - 1))

📝 Points essentiels

• La méthode récursive pour une suite d’ordre 1 repose sur la relation $u_{n+1} = f(u_n)$ et une condition d’arrêt à $n=0$, où la valeur initiale $u_0$ est renvoyée. La récursion s’effectue en appelant la fonction pour $n-1$, puis en utilisant la valeur retournée pour calculer $u_n$.

• La construction récursive de la liste des termes $[u_0, ..., u_n]$ consiste à appeler la fonction pour $n-1$, récupérer la liste jusqu’à $u_{n-1}$, puis ajouter $u_n = f(u_{n-1})$. Cela permet de visualiser la progression de la suite et d’obtenir tous ses termes.

• La comparaison avec l’approche itérative montre que la complexité en temps et en espace est similaire (linéaire en $n$), mais la récursion nécessite plus de mémoire en raison de la pile d’appels, ce qui peut poser des limites pratiques pour de grandes valeurs de $n$.

• La condition d’arrêt à $n=0$ est essentielle pour éviter une récursion infinie et assurer la convergence de la méthode. Elle correspond à la valeur initiale de la suite.

• Exemple de code Python illustrant la récursion pour une suite d’ordre 1 :

def u_rec(f, u0, n):
    if n == 0:
        return u0
    else:
        return f(u_rec(f, u0, n - 1))

💡 À retenir

La récursion pour une suite d’ordre 1 repose sur une relation de récurrence avec une condition d’arrêt claire, permettant de calculer efficacement chaque terme, tout en étant comparable à l’approche itérative en termes de complexité, mais avec une consommation mémoire plus importante.

📖 10. Suite récurrente ordre 2

🔑 Notions clés & Définitions

• Suite récurrente d’ordre 2 : Suite de nombres définie par une relation de récurrence impliquant deux termes précédents, généralement de la forme un+2 = f(un, un+1), où f : R² → R.
• Exemple particulier (suite de Fibonacci) : Suite où f(x, y) = x + y, avec u0 et u1 donnés, et un+2 = un + un+1.
• Calcul itératif du n-ième terme : Méthode consistant à partir des deux premiers termes, appliquer la relation de récurrence de façon successive pour obtenir un sans recours à la récursivité, en utilisant une boucle.
• Fonction u_it pour suites d’ordre 2 : Fonction qui, à partir de f, u0, u1 et n, calcule un en utilisant une approche itérative, en mettant à jour deux variables représentant un et un+1 à chaque étape.
• Avantages de l’approche itérative : Simplicité de mise en œuvre, efficacité en termes de complexité spatiale (mémoire constante), évite la croissance exponentielle des appels récursifs, et limite le risque d’erreur de dépassement de pile.

📖 11. Exponentiation naïve

🔑 Notions clés & Définitions

• Exponentiation naïve par multiplication répétée : méthode consistant à calculer $x^n$ en multipliant $x$ par lui-même $n$ fois, selon la relation $x^n = \prod_{k=1}^n x$.
• Implémentation simple et directe de la puissance : approche consistant à coder la multiplication répétée de manière itérative ou récursive, sans optimisation, pour obtenir $x^n$.
• Complexité temporelle linéaire en exposant : caractéristique de l'algorithme naïf où le nombre d'opérations (multiplications) est proportionnel à $n$, donc $O(n)$.
• Limites pour grands exposants : inefficacité de la méthode naïve lorsque $n$ devient très grand, entraînant un nombre élevé d'opérations et un coût computationnel important.
• Exemple de code Python pour exponentiation naïve : code simple utilisant une boucle ou une récursion pour calculer $x^n$ en multipliant $x$ par lui-même $n$ fois.

📝 Points essentiels

L'exponentiation naïve consiste à multiplier $x$ par lui-même $n$ fois, ce qui correspond à une implémentation directe de la définition mathématique $x^n = x \times x \times \dots \times x$ (n facteurs). Cette méthode est simple à coder, par exemple avec une boucle :

def puissances_it(x, n):
    result = 1
    for _ in range(n):
        result *= x
    return result

ou en récursion :

def puissances_rec(x, n):
    if n == 0:
        return 1
    else:
        return x * puissances_rec(x, n - 1)

Cependant, cette approche a une complexité temporelle linéaire $O(n)$, ce qui devient rapidement inefficace pour de grands $n$. La limite principale est la consommation de temps et de ressources pour des exposants très grands, rendant cette méthode peu adaptée en pratique pour des calculs intensifs.

💡 À retenir

L'exponentiation naïve par multiplication répétée est une méthode simple mais inefficace pour de grands exposants, car sa complexité est linéaire en $n$. Elle sert principalement à illustrer la définition de l'exponentiation, mais doit être remplacée par des méthodes plus efficaces pour des applications pratiques.

📖 12. Exponentiation rapide récursive

🔑 Notions clés & Définitions

• Exponentiation rapide récursive : méthode d’évaluation de xⁿ utilisant la décomposition binaire de l’exposant n, permettant de réduire le nombre de multiplications en divisant n par 2 à chaque étape, et en utilisant la récursion pour implémenter cette décomposition (voir section 3-6).

• Réduction du nombre de multiplications : principe selon lequel l’algorithme divise n par 2 à chaque étape, exploitant la relation (xⁿ) = (x^(n/2))² si n est pair, et x × (x^((n−1)/2))² si n est impair, pour limiter le nombre d’opérations (voir section 3-6).

• Complexité logarithmique en exposant : caractéristique de l’algorithme, indiquant que le nombre d’opérations est proportionnel à log₂(n), ce qui optimise considérablement le calcul par rapport à une exponentiation naïve (voir section 3-6).

• Utilisation de la récursion : procédé où la fonction s’appelle elle-même avec un exposant réduit, permettant d’implémenter efficacement la décomposition binaire de n, tout en conservant une structure simple et claire (voir section 3-6).

• Décomposition binaire de l’exposant : représentation de n en base 2, permettant d’identifier les puissances de deux qui composent n, et d’optimiser le calcul de xⁿ en combinant ces puissances via la récursion (voir section 3-6).

📝 Points essentiels

L’algorithme d’exponentiation rapide récursive repose sur la décomposition binaire de l’exposant n, ce qui permet de réduire le nombre d’opérations de multiplication à une proportion logarithmique en n. La relation fondamentale est :

• Si n est pair, xⁿ = (x^(n/2))²
• Si n est impair, xⁿ = x × (x^((n−1)/2))²

Cette méthode exploite la propriété que l’on peut diviser n par 2 à chaque étape, ce qui limite la profondeur de la récursion à log₂(n). La récursion s’arrête lorsque n atteint 0, où x⁰ = 1. La réduction du nombre de multiplications permet d’obtenir une complexité en O(log n), bien plus efficace que la méthode naïve en O(n). La mise en œuvre récursive est simple : à chaque appel, on divise n par 2, puis on combine les résultats selon la parité de n.

Exemple de code Python pour exponentiation rapide récursive :

def fast_power(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half = fast_power(x, n // 2)
        return half * half
    else:
        return x * fast_power(x, n - 1)

💡 À retenir

L’exponentiation rapide récursive exploite la décomposition binaire de l’exposant pour réduire le nombre d’opérations à un ordre logarithmique, rendant le calcul de puissances très efficace tout en utilisant la récursion pour une implémentation élégante et simple.

📊 Tableaux de Synthèse

Thème	Description	Exemple / Code / Auteur
Fonction récursive	Fonction qui s'appelle elle-même pour résoudre un problème en décomposant en sous-problèmes.	Généralisations, Généralités
Condition d'arrêt	Critère pour stopper la récursion, évitant boucle infinie.	n == 0 dans factorielle
Appel récursif	Invocation de la fonction dans sa propre définition, décomposant le problème.	return n * fact_rec(n - 1)
Relation de récurrence	Formulation mathématique traduite en code récursif.	n! = n * (n-1)!
Complexité Fibonacci naïve	Exponentielle, O(2^n), due à la redondance des calculs.	-
Mémoïsation Fibonacci	Technique pour éviter la recomputation, réduisant la complexité à O(n).	Stockage des résultats intermédiaires
Suite récurrente ordre 1	Définie par une seule précédente, comme u(n) = a*u(n-1) + b.	-
Suite récurrente ordre 2	Dépend des deux termes précédents, comme u(n) = p*u(n-1) + q*u(n-2).	-
Exponentiation naïve	Calcul de a^n par multiplication répétée, complexité O(n).	-
Exponentiation rapide récursive	Technique divisant par 2 l'exponentiation, complexité O(log n).	Algorithme de "dichotomie"

⚠️ Pièges & Confusions Fréquentes

1. Confondre appel récursif et boucle itérative : la récursion utilise des appels de fonction, pas une boucle.
2. Oublier la condition d'arrêt, entraînant une récursion infinie et une erreur de dépassement de pile.
3. Mal définir la relation de récurrence, ce qui conduit à des résultats incorrects ou inefficaces.
4. Confondre la complexité exponentielle de Fibonacci naïve et la version optimisée par mémoïsation.
5. Sous-estimer la consommation mémoire de la pile lors de récursions profondes.
6. Mal utiliser la mémoïsation, en oubliant de stocker ou de réutiliser les résultats intermédiaires.
7. Confondre suite récurrente d’ordre 1 et 2, ou ne pas respecter la relation de dépendance.
8. Mal implémenter l'exponentiation rapide, en ne divisant pas correctement l'exposant.

✅ Checklist Examen

• Connaître la définition de la fonction récursive selon Généralités.
• Savoir identifier la condition d'arrêt dans une fonction récursive.
• Expliquer le rôle des appels récursifs dans la décomposition du problème.
• Traduire une relation de récurrence mathématique en code récursif.
• Illustrer la différence entre approche itérative et récursive.
• Décrire la structure d'une fonction récursive avec ses éléments fondamentaux.
• Comprendre le fonctionnement de la fonction factorielle récursive en Python.
• Expliquer comment la récursion peut entraîner une complexité exponentielle, notamment pour la suite de Fibonacci naïve.
• Définir la technique de mémoïsation et ses avantages pour la complexité.
• Représenter un arbre d'appels récursifs pour une fonction donnée.
• Maîtriser la différence entre suite récurrente d’ordre 1 et 2.
• Savoir implémenter une exponentiation naïve et une exponentiation rapide récursive.
• Connaître la relation de récurrence pour une suite d’ordre 2.