C4.1 : Récursivité

Présentation

Première approche

• Considérons le code suivant : 

def afficheNombres(debut, fin):
    if debut > fin:
        print("FIN")
    else:
        print(debut)
        afficheNombres(debut+1, fin)

afficheNombres(20, 24)

A faire : dérouler le programme "à la main" (sans utiliser l'ordinateur) et expliquer ce qu'il va afficher dans le shell.

• Considérons maintenant le code précédent, légèrement modifié comme suit :

def afficheNombres(debut, fin):
    if debut > fin:
        print("FIN")
    else:
        print(debut)
        afficheNombres(debut+1, fin)
        print("Après ", debut)

afficheNombres(20, 24)

A faire : dérouler le programme "à la main" (sans utiliser l'ordinateur) et expliquer ce qu'il va afficher dans le shell.

Bilan d'étape

Généralités

Une fonction récursive s’appelle elle-même

Lors d’une récursivité, les instructions (ou portions d’instructions) en attente sont placées dans une pile puis dépilées.

C’est pour cela que la récursion peut nécessiter beaucoup de mémoire (En Python, par défaut, la pile est de taille 1000 au maximum).

Pour qu'un programme qui appelle une fonction récursive se termine, il est nécessaire que la fonction récursive contienne une condition, dite condition d'arrêt :

  • - si la condition d'arrêt est vérifiée, la fonction n'est pas rappelée et le code correspondant au cas de base est exécuté ;
  • - si la condition d'arrêt n'est pas vérifiée, le code contenant l'appel récursif à la fonction est exécuté.

Méthodologie :

  • 1) Repérer le sous-problème qui se répète, à un « niveau inférieur », ou « imbriqué ».
  • 2) Repérer la condition d’arrêt, et le cas de base.

Bien comprendre la pile de récursivité (ou pile d'exécution)

https://visualiseur-recursivite.forge.apps.education.fr/

A faire : observer les deux codes avec le mode "Pas à pas" de Thonny.

A faire : observer les deux codes dans PythonTutor.

A faire : observer les deux codes dans Visualiseur de récursivité.

Application

Application n° 1 : afficher les nombres par ordre décroissant

Proposer deux fonctions récursives à un seul paramètre n qui permettent, pour l'une d'afficher les nombres de 1 à n, pour l'autre d'afficher les nombres de n à 1.

Application n° 2 : afficher les puissances de 2

Proposer une fonction récursive qui permet d'afficher les n premières puissances de 2.

Application n° 3 : "Bonjour !"

Écrire une fonction récursive qui affiche n fois le message "Bonjour !".

Application n° 4 : carrés emboités

En utilisant le module PIL, écrire un programme avec :

Fonctions récursives avec renvoi d'une valeur

Analyse d'un code

On considère le code ci-dessous :

def s(n:int) -> int:
    if n == 0:
        return 0
    else:
        return n + s(n-1)

1) Quelle valeur va renvoyer s(5) ?

2) Détailler le déroulement pas à pas du programme en précisant les instructions stockées dans la pile d'appel (pile d'exécution).

Deux exemples pour commencer

Application n° 1 : Factoriel

En mathématique, la fonction "factoriel(n)" renvoie le produit des nombres de 1 à n.

Ainsi :

On souhaite programmer cette fonction.

On observe que factoriel(n) = n * factoriel(n-1). Ainsi, la fonction pourra être récursive.

Proposer une fonction récursive qui permet de calculer factoriel n pour n ≥ 0.

Application n° 2 : 2 à la puissance n

A faire : proposer une fonction récursive qui prend un nombre entier n en paramètre et revoie 2 à la puissance n. Cette fonction ne devra pas utiliser l'opérateur **, mais seulement l'opérateur *.

Autres applications

Application n° 1 : Inverser une chaine de caractères

Écrire une fonction récursive qui prend une chaine de caractères en paramètre et renvoie une chaine avec les caractères dans l'ordre inverse.

Information

Si ch est une chaine :

  • • ch[i:j] renvoie la sous-chaine qui va du caractère en position i au caractère en position j - 1  ;
  • • ch[:j] renvoie la sous-chaine qui va du premier caractère au caractère en position j - 1;
  • • ch[i:] renvoie la sous-chaine qui va du caractère en position i au dernier caractère.

Application n° 2 : Conversion de la base 10 à la base 2

Écrire une fonction récursive qui prend un nombre entier en base 10 en paramètre et renvoie une chaine de caractères correspondant à la valeur en binaire de l'entier.

Application n° 3 : Somme des chiffres d'un entier positif

Écrire une fonction récursive qui prend un nombre entier en paramètre et renvoie la somme des chiffres de cet entier.

Applications plus complexes

Application n° 1 : Être ou ne pas être une puissance de 2

Écrire une fonction récursive estPuissance2(n) qui renvoie True si n (entier strictement positif) est une puissance de 2 et False sinon.

Application n° 2 : Être ou ne pas être un palindrome

Écrire un fonction récursive qui renvoie True si la chaine de caractères passée en paramètre est un palindrome et False dans le cas contraire.

Application n° 3 : Tirage du loto

A faire : écrire une fonction pour faire le tirage des 6 numéros du loto à l’aide d’une fonction récursive. Les 6 numéros doivent être différents et compris entre 1 et 49. La fonction prendra en paramètre une liste de numéros déjà tirés. Ainsi, le tirage du loto sera lancé par loto([]).