Récursivité - NSI / Terminale

« Chapitre no 1 Récursivité I.

Exemple : calcul de la factorielle d’un entier naturel ( La factorielle d’un nombre entier naturel n, notée n !, est définie par n ! = 1 si n = 0 n × · · · × 1 si n ∈ N∗ Exercice no 1 Dans un fichier exercice1.py, écrire et tester la fonction fact(n) calculant n ! où n est un entier naturel. Aide : On utilisera une boucle while. N Notons f la fonction définie sur par f (n) = n !. ¡ ¢ Lorsque n Ê 1, on a : f (n) = n × (n − 1) × · · · × 1 = n × (n − 1) × · · · × 1 = n × (n − 1) ! = n × f (n − 1).

D’où f (n) = n ! = ( 1 si n = 0 n × f (n − 1) si n ∈ N∗ (relation de récurrence) Le calcul de f (n) se ramène alors au calcul de f (n − 1) et l’écriture de la fonction factorielle en python s’écrit naturellement : def fact(n): if n == 0: return 1 else: return n * fact(n-1) Description de l’algorithme pour n=4 Pour calculer la valeur renvoyée par fact(4), il faut appeler fact(3).

Cet appel déclenche les appels de fact(2) puis de fact(1) et enfin de fact(0).

Cette succession d’appels est représentée par l’arbre d’appels suivant : fact(4) 24 return 4× fact(3) 4×6 return 3× fact(2) 3×2 return 2× fact(1) 2×1 return 1× fact(0) 1×1 return 1 On observe la construction d’une pile d’appels successifs de la fonction.

Chaque appel possède son propre environnement et ses propres variables stockés en mémoire (la pile). Juste après le dernier appel à fact(0), la pile contient les environnements d’exécution des cinq appels à la fonction fact. Pour un appel initial fact(n), il y aura n + 1 environnements dans la pile. Terminaison de l’algorithme • Pour n = 0 la fonction renvoie le résultat à savoir 1. • Sinon à chaque appel récursif, la valeur passée en paramètre dans la fonction diminue de 1.

Donc au bout de n + 1 appels cette valeur est égale à 0.

Ce qui entraîne, en vidant peu à peu la pile des appels récursifs, la fin du programme. Complexité de l’algorithme Pour un entier naturel n, notons c n le nombre d’opérations nécessaires au calcul de fact(n). • Pour n = 0, il y a un test donc c 0 = 1. • Pour n Ê 1, il y a un test, une multiplication et l’appel de la fonction avec comme paramètre n − 1 donc le nombre d’opérations c n−1 .

Donc on a la relation de récurrence : c n = 2 + c n−1 . (c n ) est une suite arithmétique de raison 2 et de premier terme c 0 = 1 donc c n = c 0 + 2n = 2n + 1. Le coût de l’algorithme est linéaire, la complexité de l’algorithme est en O(n) II.

Fonctions récursives Définition no 1 Une fonction est dite récursive lorsqu’elle s’appelle elle-même dans sa propre définition. Principe : La formulation récursive d’une fonction est constituée : • de cas de base où il n’y a pas d’appel de la fonction ce qui permet de sortir de la récursivité. Ce sont généralement le cas des valeurs particulières où il est facile de déterminer un résultat. Dans l’exemple précédent le cas de base est défini lorsque n = 0. • de cas récursifs qui sont ceux qui renvoient à la fonction. " Attention En Python la taille de la pile des appels récursifs est limitée.

Si la récursivité est trop profonde on déclenche une RecursionError.

La valeur de la pile peut être obtenue par : import sys sys.getrecursionlimit() Pour changer cette limite et passer à 2000 appels par exemple, on exécute le code suivant : import sys sys.setrecursionlimit(2000) Exercice no 2 1.

Dans le fichier exercice2.py, écrire la fonction récursive de l’exemple précédent. 2.

Préciser quels sont les cas de base et récursif. 3.

Modifier le code afin de pouvoir calculer 2000 !. Avantages et inconvénients de la récursivité • très économique pour le programmeur : ∗ proche d’une description mathématique (relation de récurrence) ; ∗ bien adaptée aux structures de données récursives (arbres, graphes, ...) • peut être très dispendieuse en ressources machine : ∗ utilisation de la mémoire pour conserver les informations relatives à la fonction en cours d’exécution. Complexité d’une fonction récursive Posons c n le coût d’une fonction récursive pour un problème de taille n où n est un entier naturel.

Pour évaluer c n , on cherche une relation de récurrence liant c n et les coûts précédents c n−1 , c n−2 , etc... Relation de récurrence c n = c n−1 + O(1) c n = c n−1 + O(n) c n = 2 × c n−1 + O(1) Complexité linéaire : O(n) ¡ ¢ quadratique : O n 2 ¡ ¢ exponentielle : O 2n Exercice no 3 Soit n un entier naturel et la fonction somme(n) = 0 + 1 + · · · + n. 1.

Recopier et compléter en fonction de somme(n −( 1) : .

.

.

si n = 0 somme(n) = .

.

.

si n ∈ ∗ N Préciser quels sont les cas de base et récursif. 2.

En déduire l’écrire en langage python, dans le fichier exercice3.py, de la fonction récursive somme(n). Exercice no 4 Soit x un nombre réel et n un entier naturel. On veut écrire une fonction récursive puissance(x, n) calculant x n . 1.

Déterminer le cas de base et le cas récursive de l’algorithme. 2.

Déterminer la complexité de l’algorithme. 3.

Écrire dans le fichier exercice4.py la fonction récursive puis la tester. Exercice no 5 On veut la fonction récursive nombre_de_chiffres(n) qui renvoie le nombre de chiffres de l’écriture d’un entier naturel n. 1.

Déterminer le cas de base et le cas récursive de l’algorithme. 2.

Écrire dans le fichier exercice5.py la fonction récursive puis la tester. Exercice no 6 : Récursion multiple Ici la fonction est définie par plusieurs cas récursifs. Par exemple en reprenant, l’exercice no 4, la fonction puissance peut être définie autrement : si n est pair, ¡ ¢2 ¡ ¢2 x n = x n/2 et si n est impair, x n = x × x (n−1)/2 .

On a alors :   si n = 0  1 pui ssance(x, n) = pui ssance(x, n/2) ∗ ∗2 si n ∈   x × pui ssance(x, (n − 1)/2) ∗ ∗2 si n ∈ N∗ et n est pair N∗ et n est impair 1.

Écrire dans le fichier exercice6.py, la fonction récursive puissance(x, n). 2.

Pourquoi cette version est-elle plus efficace ? III.

Récursivité terminale Une fonction récursive est dite terminale lorsque l’appel récursif est la dernière instruction exécutée. Dans la fonction récursive fact(n), la dernière exécution est n×fact(n-1) (le produit) donc cette fonction n’est pas récursive terminale.

On modifie la fonction afin qu’elle devienne récursive terminale, de la façon suivante : def fact(n, acc=1): if n == 0: return acc else: return fact(n-1, acc * n) L’avantage est qu’il n’y a pas de calculs en attente et donc qu’il n’y a rien à mémoriser dans la pile. Exercice no 7 Reprendre les exercices no 3 et no 5 et pour chacun d’entre eux écrire les fonctions récursives terminales dans le fichier exercice7.py. Exercice no 8 : Conjecture de Syracuse N par un+1 = ( u n /2 si u n est pair avec u 0 entier supérieur à 1. 3 × u n + 1 sinon Écrire dans le fichier exercice8.py, la fonction récursive syracuse(u) qui affiche les valeurs successives de (u n ) tant que (u n ) est supérieur à 1. Soit (u n ) la suite d’entiers définie sur Exercice no 9 : Algorithme Glouton : épreuve pratique 2022 On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets. Le système monétaire est donné sous forme d’une liste : pieces=[100, 50, 20, 10, 5, 2, 1] (on supposera qu’il n’y a pas de limitation quant à leur.... »