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

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

A faire : observer le deuxième code avec le mode "Pas à pas" de Thonny.

A faire : observer le deuxième code dans PythonTutor.

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.

def aff_croissant(n):
    if n == 0:
        print("Cas d'arrêt")
    else:
        aff_croissant(n-1)
        print(n)

def aff_decroissant(n):
    if n == 0:
        print("Cas d'arrêt")
    else:
        print(n)
        aff_decroissant(n-1)

# Prgramme principal
print("Affichage croissant")
aff_croissant(5)
print("Affichage décroissant")
aff_decroissant(5)

Application n° 2 : afficher les puissances de 2

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

def aff_puiss(n):
    if n == 0:
        print("Cas d'arrêt")
    else:
        aff_puiss(n-1)
        print(n**2)

# Prgramme principal
aff_puiss(5)

Application n° 3 : "Bonjour !"

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

def aff_bonjour(n):
    if n == 0:
        pass
    else:
        print("Bonjour")
        aff_bonjour(n-1)

# Prgramme principal
aff_bonjour(5)

Application n° 4 : carrés emboités

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

• - une fonction qui permet de tracer un rectangle centré de côté c passé en paramètre ;
• - une fonction recursive qui permet de tracer l'ensemble des carrés comme le montre l'image ci-dessous ;
• - le corps du programme.

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 :

• factoriel(0) = 1 (Par définition)
• factoriel(1) = 1 (Par définition)
• factoriel(2) = 2
• factoriel(3) = 6
• factoriel(4) = 24
• ...

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.

def fact(n):
    """
    Renvoie factoriel(n) pour tout entier n >= 0
    """
    if n <= 0:
        return 1
    else:
        return n * fact(n-1)

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 *.

def puiss2(n):
    """
    Renvoie 2^n pour tout entier positif ou nul n
    """
    if n == 0:
        return 1
    else:
        return 2 * puiss2(n-1)

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

def invChaine_rec(c):
    if len(c) <= 1:
        return c
    else:
        return invChaine_rec(c[1:]) + c[0]

def invChaine_rec(c):
    if len(c) <= 1:
        return c
    else:
        return c[-1] + invChaine_rec(c[1:-1]) + c[0]

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.

def decToBin_rec(nb):
    """
    Converti un nombre décimal en un nombre binaire écrit dans une chaine de caractères.
    """
    if nb < 2:
        return str(nb)
    else:
        return decToBin_rec(nb // 2) + str(nb % 2)

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.

def somChiffres_rec(nb):
    """
    Renvoie la somme des chiffres d'un nombre entier positif"
    """
    if nb < 10:
        return nb
    else:
        return nb % 10 + somChiffres_rec(nb // 10)

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.

def estPuissance2(n:int) ->bool:
    """
    Teste si un entier positif ou nul est une puissance de 2
    Paramètres
        n (int) : entier positif ou nul
    Valeur renvoyée
        (bool) : True si le paramètre est une puissance de 2 et False sinon

    """
    if n == 0:
        return False
    elif n == 1:
        return True
    elif n % 2 == 1:
        return False
    else:
        return estPuissance2(n/2)

assert estPuissance2(10) == False
assert estPuissance2(8) == True
assert estPuissance2(4) == True
assert estPuissance2(2) == True
assert estPuissance2(1) == True
assert estPuissance2(0) == False

print('Tous les tests sont passés')

Application n° 5 : Ê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.

def estPalindrome(mot:str)->bool:
    """
    Teste si un mot est un palindrome
    Paramètres
        n (str) : chaine de caractères
    Valeur renvoyée
        (bool) : True si le paramètre est un palindrome et False sinon

    """
    if len(mot) < 2:
        return True
    elif mot[0] != mot[-1]:
        return False
    else:
        return estPalindrome(mot[1:-1])

assert estPalindrome("kayak") == True
assert estPalindrome("w") == True
assert estPalindrome("bb") == True
assert estPalindrome("az") == False
assert estPalindrome("ici") == True
assert estPalindrome("nsi") == False

print('Tous les tests sont passés')

Application n° 6 : 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([]).

from random import randint

def loto(tirage):
    if len(tirage) == 6:
        return tirage
    else:
        val_ok = False
        while not val_ok:
            val = randint(1,49)
            if not val in tirage:
                val_ok = True
        return loto(tirage + [val])

print(loto([]))