TD1 : Exercices d'introduction à la récursivité

⚠ Exercices de base à bien maîtriser à la fin du chapitre.

✏️ Partie A — Sans coder

Exercice 1 : Comprendre le comportement d'une fonction récursive.

On donne les fonctions suivantes :

```
def f(n):
    return n * f(n - 1)
```
Que se passe-t-il si on appelle f(3) ?

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

Que se passe-t-il si on appelle g(3) ?

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

Que se passe-t-il si on appelle h(3) ?

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

Que se passe-t-il si on appelle p(3) ?

Exercice 2 : Trouver l'erreur.

Chacune des fonctions suivantes contient une erreur. Sans utiliser l'ordinateur, expliquez ce qui se passe (ou ce qui est faux) lors de l'appel proposé, puis corrigez la fonction sur votre cahier.

```
def somme_jusqua(n):
    if n == 1:
        return 0
    return n + somme_jusqua(n - 1)
```
Cette fonction doit calculer 1 + 2 + ... + n. Que renvoie l'appel somme_jusqua(3) ? Est-ce le résultat attendu ?
```
def multiplication(a, n):
    if n == 1:
        return a
    multiplication(a, n - 1) + a
```
Cette fonction doit calculer a × n (en n'utilisant que des additions). Que renvoie l'appel multiplication(3, 4) ?
```
def factorielle_bis(n):
    if n == 1:
        return 1
    else:
        return n * factorielle_bis(n - 1)
```
Cette fonction fonctionne correctement pour calculer n! lorsque n >= 1. Que se passe-t-il si on appelle factorielle_bis(0) ?

Exercice 3 : Dérouler une pile d'appels à la main.

En reprenant la fonction g de l'exercice 1, dessinez la pile d'exécution pour l'appel g(4) (sur le modèle de la figure vue en cours pour factorielle(5)) : détaillez chaque appel empilé, puis chaque valeur obtenue lors du dépilement, jusqu'au résultat final.

Exercice 4 : Arbre des appels récursifs.

On considère la fonction suivante :

def mystere(n):
    if n <= 1:
        return 1
    return mystere(n - 1) + mystere(n - 1)

Dessinez l'arbre de tous les appels récursifs déclenchés par mystere(3) (chaque appel apparaît comme une "boîte" qui en déclenche deux autres, jusqu'aux cas d'arrêt), puis comptez le nombre total d'appels effectués. Que devient ce nombre pour mystere(4) ? Que pensez-vous du nombre d'appels quand n augmente ?

Exercice 5 : Trouver la relation de récurrence.

Pour chacune des situations suivantes, calculez "à la main" les premiers termes demandés, puis écrivez la relation de récurrence qui permet de passer d'un terme au suivant (vous n'avez pas besoin d'écrire de fonction Python pour cet exercice).

Division cellulaire : une bactérie se divise en 2 toutes les heures. On part d'une seule bactérie. Calculez le nombre de bactéries B(1), B(2), B(3), puis écrivez la relation de récurrence entre B(n) et B(n - 1).
Triangles d'allumettes : on construit une rangée de triangles équilatéraux accolés avec des allumettes (chaque nouveau triangle partage un côté avec le précédent). On note T(n) le nombre d'allumettes à la profondeur n. Faites un dessin pour les 3 premiers triangles, comptez le nombre d'allumettes T(1), T(2), T(3), puis écrivez la relation de récurrence entre T(n) et T(n - 1).
Poignées de main : n personnes sont dans une pièce et chacune serre la main de toutes les autres, une seule fois. On note H(n) le nombre total de poignées de main échangées.
- Commencez par H(2) (2 personnes) : combien de poignées de main ?
- Puis H(3) : les 2 premières personnes ont déjà échangé leurs poignées de main (H(2) poignées), la 3^e personne qui arrive doit encore serrer la main des 2 personnes déjà présentes. Combien cela fait-il en plus ? En déduire H(3).
- Faites de même pour passer de H(3) à H(4) : combien de nouvelles poignées de main la 4^e personne doit-elle échanger avec les personnes déjà présentes ?
- En déduire la relation de récurrence entre H(n) et H(n - 1).
Segments du flocon de von Koch On part d'un unique segment et on note S(n) le nombre de segments à la profondeur n (c'est la profondeur 0, donc S(0) = 1). Pour passer d'une profondeur à la suivante, chaque segment de la figure est "cassé" en 3 parties égales, et le segment du milieu est remplacé par 2 segments "obliques" (formant un triangle équilatéral sans base) — un segment devient donc 4 segments plus petits.
- Faites un dessin : dessinez le segment unique de profondeur 0, puis dessinez ce qu'il devient à la profondeur 1 en appliquant la règle ci-dessus En déduire S(1).
- À la profondeur 2, la règle s'applique à nouveau, mais cette fois à chacun des segments obtenus à la profondeur 1 Combien de nouveaux segments obtient-on à partir d'un seul segment ? En déduire S(2), puis S(3).
- En déduire la relation de récurrence entre S(n) et S(n - 1).

💻 Partie B — Du Python pour coder des fonctions récursives !

Pour tous les exercices suivants, il faut déterminer des fonctions récursives, donc il faut à chaque fois trouver la condition d'arrêt et une relation de récurrence pour l'appel récursif.

Exercice 1 : Un grand classique.

La (fameuse) suite de Fibonacci est une suite d'entiers telle que les deux premiers termes sont 0 et 1 et que chaque terme de la suite à partir du troisième s'obtient en faisant la somme des deux précédents.

Les premiers termes de la suite de Fibonacci sont donc : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

On peut donc la définir par récurrence (en notation mathématique) par :

F₀ = 0, F₁ = 1 et pour tout n > 1, F_n = F_{n
- 1} + F_{n - 2}

Écrire une fonction récursive fibonacci qui prend en paramètre un entier naturel n et qui renvoie la valeur de F_n (avec n un entier naturel).

Exercice 2 :

1. Écrire une fonction récursive puissance qui élève un nombre flottant x à une puissance entière positive n. On ne demande pas de traiter le cas 0⁰.

On commencera par trouver une relation de récurrence, c'est-à-dire le rapport entre xⁿ et x^{n - 1}.

2. Écrire la version itérative (avec une boucle) de la fonction demandée ci-dessus.

Exercice 3 :

1. Soit n un entier naturel. Écrire une fonction récursive gauss qui prend en paramètre un entier naturel n et qui calcule la somme 0 + 1 + 2 + ... + n.

On commencera par trouver une relation de récurrence, c'est-à-dire le rapport entre gauss(n) et gauss(n - 1).

2. Écrire la version itérative de la fonction demandée ci-dessus.

Exercice 4 :

1. En 2021, dans une forêt, on estime le nombre d'arbres à 50 000. Tous les ans, environ 5% des arbres disparaissent et l'organisme d'entretien des forêts en replante 3 000. Écrire une fonction récursive nb_arbres qui permette de connaître une valeur approchée (en milliers d'arbres) du nombre d'arbres dans n années.

On commencera par écrire la relation de récurrence entre u_n et u_{n - 1}.

2. Écrire la version itérative de la fonction demandée ci-dessus.

Exercice 5 :

1. Écrire une fonction récursive somme qui prend en paramètres 2 entiers naturels m et n et renvoie la somme de ces 2 entiers. La seule opération dont on dispose est l'ajout de 1 à un entier a, c'est-à-dire a + 1.

2. Écrire une fonction récursive produit qui prend en paramètres 2 entiers naturels m et n et qui renvoie le produit de ces 2 entiers.

Exercice 6 :

Écrire une fonction récursive nb_pairs qui prend en paramètre un entier n strictement positif (n ≥ 1) et qui affiche les entiers pairs de 0 à n inclus par ordre décroissant.

Remarque : cette fonction ne doit rien renvoyer, elle doit uniquement afficher des entiers.

Exercice 7 :

1. Écrire une fonction récursive longueur_liste qui prend en paramètre une liste tab et qui renvoie le nombre d'éléments de cette liste (bien sûr la fonction len est interdite).

Remarque : on pourra utiliser les slices ([1:] ou [:-1]) ou éventuellement écrire une fonction qui "détruit" la liste passée en paramètre du moment qu'elle retourne bien le bon nombre d'éléments.

2. Écrire une fonction récursive longueur_chaine qui prend une chaîne de caractères ch en paramètre et qui renvoie la longueur de ch.

Exercice 8 :

Écrire une fonction récursive pair qui prend en paramètre un entier naturel n et qui teste si n est un nombre pair (elle renvoie True ou False).

Exercice 9 :

Écrire une fonction récursive dernier_element_liste qui prend une liste non vide tab en paramètre et qui renvoie le dernier élément de la liste.

Exercice 10 :

Un palindrome est une chaîne de caractères qui est identique lue de gauche à droite ou de droite à gauche. Par exemple, la chaîne RADAR est un palindrome : si on inverse le mot, il reste identique.

Pour coder récursivement un test de palindrome, il faut donc vérifier que :

les lettres aux extrémités sont les mêmes ;
le mot privé de ses deux extrémités est encore un palindrome, d'où appel récursif.

Écrire une fonction récursive palindrome qui prend en paramètre une chaîne de caractères ch et qui permet de vérifier si ch est palindrome (elle renvoie True ou False).

Exercice 11 :

Écrire une fonction récursive in_liste qui prend en paramètres une liste de nombres entiers et un nombre entier et qui renvoie True si le nombre est dans la liste et False sinon.

Exercice 12 :

Écrire une fonction récursive somme_liste qui prend en paramètre une liste de nombres tab et qui renvoie la somme de ces nombres.

Exercice 13 :

Écrire une fonction récursive test_croissant qui prend en paramètre une liste de nombres tab et qui renvoie True si la liste est triée par ordre croissant et False sinon.

Exercice 14 :

Écrire une fonction récursive nb_occurrences qui prend en paramètres une chaîne de caractères ch et un caractère car et qui renvoie le nombre d'occurrences de ce caractère dans la chaîne (c'est-à-dire le nombre de fois que car apparaît dans la chaîne).

Exercice 15 :

Écrire une fonction récursive premiere_occurrence qui prend en paramètres une chaîne de caractères ch et un caractère car et qui renvoie l'indice de la première occurrence du caractère dans la chaîne de caractères. Si le caractère n'est pas dans la chaîne, elle doit renvoyer -1.

Exercice 16 :

Écrire une fonction récursive somme_chiffres qui prend en paramètre un entier naturel n et qui calcule la somme des chiffres de n.

Exercice 17 :

En mathématiques, la série harmonique est la somme des inverses des entiers naturels non nuls.

H_n = 1 + 1/2 + 1/3 + ... + 1/n

Écrire une fonction récursive harmonique qui prend en paramètre un entier naturel n et qui calcule la somme harmonique de n.

Exercice 18 :

Écrire une fonction récursive recherche_dicho qui prend en paramètre une liste triée tab, un élément elt (et 2 autres paramètres à trouver) et qui effectue une recherche dichotomique dans le tableau trié. Elle renvoie l'indice si l'élément est dans la liste et -1 sinon.

Exercice 19 : Suite de Collatz

On choisit un entier naturel u₀. La suite u_n est alors définie par récurrence par : u_n = u_{n - 1} / 2 si u_{n - 1} est pair et u_n = 3u_{n - 1} + 1 s'il est impair. Il semble que, quel que soit l'entier naturel choisi pour u₀, cette suite arrive toujours à la valeur 1 (puis elle devient cyclique).

Par exemple si on choisit n = 12, les termes successifs sont : 6, 3, 10, 5, 16, 8, 4, 2, 1, ... (on arrête quand on trouve 1).

Pour n = 13, les termes successifs sont : 40, 20, 10, 5, 16, 8, 4, 2, 1, ...

Écrire une fonction récursive collatz qui permet de vérifier cette conjecture.