Fiche de révision : Fonctions récursives en Python

📋 Plan du Cours

1. Principe de la récursivité
2. Somme des entiers
3. Factorielle et puissance
4. Pile des appels récursifs
5. Règles des tours de Hanoï
6. Résolution récursive de Hanoï

📖 1. Principe de la récursivité

🔑 Notions clés & Définitions

• Fonction récursive : Fonction qui fait appel à elle-même lors de son exécution.

📝 Points essentiels

📌 L'écriture d'une fonction récursive distingue un ou plusieurs cas récursifs, dans lesquels la fonction s'appelle avec de nouveaux arguments, et un ou plusieurs cas de base, qui terminent les appels successifs.

• Une fonction récursive doit identifier explicitement son ou ses cas de base et son ou ses cas récursifs.

💡 Astuce mémo

Cas récursif = continuer ; cas de base = arrêter

📖 2. Somme des entiers

🔑 Notions clés & Définitions

• Fonction somme : Détermine la somme des entiers compris entre a et b, avec a inférieur ou égal à b, et renvoie un entier total.

📝 Points essentiels

• La version itérative de la fonction somme initialise total à 0, parcourt les valeurs de a à b inclus avec une boucle for, ajoute chaque valeur à total, puis renvoie total.

• La fonction somme reçoit a comme entier et b comme entier supérieur ou égal à a, puis renvoie total comme entier.

💡 Astuce mémo

Parcourir les entiers de a à b puis accumuler

📖 3. Factorielle et puissance

🔑 Notions clés & Définitions

• Fonction factorielle : Détermine le produit des entiers compris entre 1 et n, où n est un entier strictement positif, et renvoie un entier fac.
• Fonction puissance : Détermine la valeur de x puissance n, avec x entier ou flottant et n entier positif, puis renvoie une valeur du même type que x.

📝 Points essentiels

• La version itérative de factorielle initialise fac à 1, parcourt les valeurs de 2 à n inclus, multiplie fac par chaque valeur, puis renvoie fac.

• La version itérative de puissance initialise val à 1, multiplie val par x à chaque valeur de k comprise entre 1 et n, puis renvoie val.

📖 4. Pile des appels récursifs

★ À maîtriser

• Pour l'appel puissance(2, 3), les appels récursifs forment une chaîne puissance(2, 3), puissance(2, 2), puissance(2, 1), puissance(2, 0), puis le cas terminal renvoie 1.

• Le nombre d'appels simultanés de fonctions est limité par la limite de récursion de Python.

📌 Dépasser la limite d'appels récursifs provoque une erreur RecursionError: maximum recursion depth exceeded in comparison.

Compléments

• La fonction getrecursionlimit du module sys permet de connaître le nombre maximal d'appels récursifs simultanés autorisés.

📌 La fonction setrecursionlimit du module sys permet de modifier la limite d'appels simultanés, mais un nombre excessif de récursions peut provoquer un plantage par débordement de la pile d'exécution.

💡 Astuce mémo

Trop d'appels simultanés → dépassement de la pile

📖 5. Règles des tours de Hanoï

🔑 Notions clés & Définitions

• Tours de Hanoï : Jeu où l'on déplace des disques de diamètres différents d'une tour gauche vers une tour droite en passant par une tour centrale, en un minimum de coups.

★ À maîtriser

• Les règles des tours de Hanoï sont les suivantes:
  • Ne déplacer qu'un seul disque à la fois
  • Placer un disque sur un disque plus grand
  • Placer un disque sur un emplacement vide

Compléments

• Les tours de Hanoï constituent un exemple de problème pouvant être résolu par une approche récursive.

📖 6. Résolution récursive de Hanoï

🔑 Notions clés & Définitions

• Procédure solution_hanoi : La procédure solution_hanoi affiche les mouvements nécessaires pour résoudre les tours de Hanoï à n disques et reçoit n, depart, intermediaire et arrivee en paramètres.

★ À maîtriser

• Pour déplacer n disques de depart vers arrivee, la procédure déplace récursivement n−1 disques vers intermediaire, déplace le plus grand disque vers arrivee, puis déplace récursivement les n−1 disques vers arrivee.

📌 Le cas de base de solution_hanoi est n égal à 0 : aucun disque n'est déplacé et la procédure ne fait rien.

Compléments

• L'appel hanoi(3, 'GAUCHE', 'CENTRE', 'DROITE') entraîne sept affichages de déplacements, dans l'ordre indiqué par la résolution récursive.

• L'objectif du chapitre est de savoir écrire une fonction récursive en identifiant ses cas de base et ses cas récursifs, puis de savoir dessiner un arbre d'appels récursifs.

💡 Astuce mémo

n−1 vers l'intermédiaire → plus grand disque → n−1 vers l'arrivée