Algorithmique II

5. Récursivité [en option]

Solutions des exercices

Exercice 1

Voir partie Apprendre.

Exercice 2

Voir partie Apprendre.

Exercice 3 – Exercice 5.3. Une question de fusion

Trier le tableau suivant avec l’algorithme de tri par fusion : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution à compléter

Exercice 4 – Exercice 5.4. Dans l’autre sens 🔌

En Python, proposer une fonction qui inverse l’ordre des lettres dans un mot. Vous pouvez parcourir les lettres du mot directement ou à travers un indice.

Proposer une autre fonction qui inverse l’ordre des lettres dans un mot de manière récursive.

Solution 4 – Exercice 5.4. Dans l’autre sens 🔌

Cliquer ici pour voir la réponse

Voici plusieurs implémentations itératives et une récursive de la fonction qui inverse un mot :

Exercice 5 – Factorielle 🔌

La fonction factorielle n! en mathématiques est le produit de tous les nombres entiers jusqu’à n. C’est une des fonctions les plus simples à calculer de manière récursive. Elle peut être définie comme ceci :

n! = (n-1)! * n

Programmer cette fonction de manière récursive en Python. Proposer également une implémentation itérative de la factorielle où les éléments de 1 à n sont traités l’un après l’autre.

Solution 5 – Factorielle 🔌

Cliquer ici pour voir la réponse

Voici une implémentation en Python de la fonction factorielle où la fonction fait appel à elle-même, sans oublier la condition d’arrêt :

Voici une implémentation en Python de la fonction factorielle qui n’est pas récursive :