Corrigé du TD Récursivité

1. Application du cours

1.1 Fonction somme

Code de la fonction :

def somme(n):
    if n == 0:
        return 0
    else:
        return n + somme(n - 1)

Question 1 :

Combien d'appels de fonction sont nécessaires pour somme(5) ? somme(n) ?

Pour somme(5) :
La fonction appelle somme(4), puis somme(3), etc., jusqu'à atteindre le cas de base somme(0).
Il y a donc 6 appels de fonction au total : somme(5), somme(4), somme(3), somme(2), somme(1), et enfin somme(0).
Pour somme(n) :
Le nombre d'appels de fonction est toujours de n + 1, car on part de somme(n) jusqu'à atteindre le cas de base somme(0).

1.2 Fonction factorielle

Code de la fonction :

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

Question 2 :

Quels seront les appels effectués pour obtenir factorielle(4) ?

Pour calculer factorielle(4), voici les appels récursifs effectués : 1. factorielle(4) appelle factorielle(3) 2. factorielle(3) appelle factorielle(2) 3. factorielle(2) appelle factorielle(1) 4. factorielle(1) appelle factorielle(0) 5. factorielle(0) retourne 1 (cas de base)

La récursion se termine alors et les valeurs remontent : - factorielle(1) retourne 1 * 1 = 1 - factorielle(2) retourne 2 * 1 = 2 - factorielle(3) retourne 3 * 2 = 6 - factorielle(4) retourne 4 * 6 = 24

2. TD

2.1 Fonction mystère

Code de la fonction :

def mystere(i, k):
    if i <= k:
        print(i)
        mystere(i + 1, k)

Question :

Que fait la fonction mystère ?

La fonction mystere(i, k) affiche tous les entiers de i à k inclus, un par un, en utilisant la récursivité. À chaque appel, elle incrémente i de 1 et réimprime jusqu'à ce que i dépasse k.

Exemple : mystere(3, 6) affichera :

2.2 Nombre de chiffres d'un nombre

Code de la fonction :

def nb_chiffre(n):
    if n < 10:
        return 1
    else:
        return 1 + nb_chiffre(n // 10)

Explication :

La fonction nb_chiffre(n) calcule récursivement le nombre de chiffres d'un nombre n. Si n est inférieur à 10, il n'a qu'un chiffre, donc elle retourne 1. Sinon, elle divise le nombre par 10 (éliminant ainsi le dernier chiffre) et ajoute 1 au résultat de l'appel récursif.

Exemples :

>>> nb_chiffre(9)
1
>>> nb_chiffre(99)
2
>>> nb_chiffre(1000)
4

2.3 Maximum d'un tableau

Code de la fonction :

def maximum(t):
    if len(t) == 1:
        return t[0]
    else:
        return max(t[0], maximum(t[1:]))

Explication :

La fonction maximum(t) utilise la récursivité pour trouver le plus grand élément d'un tableau. Si le tableau ne contient qu'un seul élément, cet élément est le maximum. Sinon, la fonction compare le premier élément du tableau avec le maximum du reste du tableau (via la tranche t[1:]), et retourne le plus grand des deux.

Exemple :

>>> maximum([3, 1, 4, 1, 5, 9])
9

3. Bonus

3.1 Suite de Syracuse

Code de la fonction :

def syracuse(u):
    print(u)
    if u > 1:
        if u % 2 == 0:
            syracuse(u // 2)
        else:
            syracuse(3 * u + 1)

Explication :

La fonction syracuse(u) génère et affiche les termes de la suite de Syracuse pour une valeur initiale u. Si u est pair, elle divise u par 2. Si u est impair, elle calcule 3 * u + 1. La fonction continue de s'exécuter jusqu'à ce que u soit inférieur ou égal à 1.

Exemple :

>>> syracuse(7)
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1