Exercices corrigés algorithme récursif

Les exercices corrigés suivants concernent le principe d’algorithme récursif, par exemple Fibonacci, les tours de Hanoï et bien d’autres cas mathématiques. Les exercices comprennent la récursion simple, la récursion terminale, la récursion croisée ou récursion mutuelle, et le principe de mémoïsation (pour plus de détail sur ce dernier point merci d’aller voir le principe de programmation dynamique).

algorithme récursif

Exercice 1

Réécrire les algorithmes suivants sous forme récursive sous forme terminal quand c’est possible.

algorithme récursif exercices corrigés récursif terminal récursité multiple arbre d'appels

algorithme récursif

algorithme récursif

Un dernier pour la route. Cette fois il faut comprendre ce qu’il fait avant de le rendre récursif terminal !

algorithme pgcd

On considère que n est un entier positif ou nul.

algorithme récursif terminal

algorithme récursif terminal

algo3 est déjà récursif mais non terminal. Puisque l’algorithme renvoit 2^n, on va changer sa structure pour le rendre terminal.

algorithme récursif terminal

Pour le dernier algorithme, il faut d’abord comprendre qu’il calcule le pgcd entre a et b. Faites un test à la main, vous comprendrez que le premier embranchement ne sert à rien, on va donc l’enlever pour la récursion. La variable r n’est pas présente pour remplacer la valeur de a et b, donc elle ne rentrera pas dans la récursion.

algorithme pgcd

Exercice 2

Le problème de Fibonacci (1170 – 1250) :

« Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? Les lapins ne meurent jamais.”

Donc si on prend un exemple les 7 premiers mois.

Mois

1

2

3

4

5

6

7

Couple

1

1

2

3

5

8

13

a – Exprimez la population de couples du mois n en fonction des mois précédents.

b – Ecrire un algorithme itératif qui calcule le nombre de couples au bout de 12 mois.

c – Modifier l’algorithme itératif pour calculer le nombre de mois au bout duquel la population de couples de lapins dépasse 300.

d – Ecrire l’algorithme récursif pour calculer le nombre de couples de lapins après n mois.

a –

Le nombre de couples de lapins au mois n est la somme des couples existants le mois d’avant (au mois n − 1) et des couples naissants au mois n.

Or, le texte précise que tous les couples existants deux mois auparavant (au mois n − 2) se reproduisent.

Par conséquent, au mois n ≥ 2 le nombre de lapins est égale à la somme du mois n-1 et n-2. Au mois 0 et au mois 1, il n’existe qu’un seul couple.

b –

Exercices corrigés algorithme récursif algorithme récursif

c –

Exercices corrigés algorithme récursif algorithme récursif

d –

algorithme récursif fibonacci

On ne calculera pas la complexité la dessus. Pour ceux qui veulent perdre la tête je vous invite ici : https://miashs-www.u-ga.fr/prevert/Prog/Complexite/nombresFibonacci.html

Exercice 3

a – Ecrire un algorithme qui calcule le maximum de 2 nombres réels 

b – Ecrire un algorithme récursif qui calcule le maximum de 3 nombres réels en utilisant l’algorithme du a. Montrer l’arbre d’appels.

c – Ecrire un algorithme récursif  qui calcule le maximum de 4 nombres réels en utilisant l’algorithme du a. Montrer l’arbre d’appels.

d – L’algorithme est-il récursif ?

a –

algorithme récursif maximum

b –

algorithme récursif maximum

Ici, Maximum2 fait office de condition terminal de l’algorithme récursif. La pile d’appels est la suivante :

algorithme récursif maximum

c –

algorithme récursif maximum

La pile d’appels est la suivante :

algorithme récursif maximum

d – Bien qu’on ait l’impression de faire une récursion, il s’agit plutôt d’une surcharge de fonction ou d’appel de fonction pour réduire la taille du problème. Ce n’est pas un algorithme récursif à proprement parler.

Exercice 4

a – Est-ce que les algorithmes ci-dessous sont des algorithmes récursifs ? 

b – Est-ce qu’ils sont terminaux ?

c – Est-ce qu’ils se terminent ?

algorithme récursif log

algorithme récursif puissance

algorithme récursif somme

a –

Les algorithmes log et somme sont récursifs : chacun contient au moins un appel à lui même, par contre, puissance ne l’est pas : il fait appel à l’algorithme puis. Il faut remplacer puis par puissance.

b – 

log est terminal, puissance et somme ne le sont pas car ils demandent un calcul lors de la récursion.

c –

log se termine pour tout entier x. L’itération de la division entière par 2 mène à 0, et le cas de base 0 se termine par l’exécution de retourner. 

Pour l’algorithme puissance (corrigé), le cas de base 0 se termine par l’excéution de retourner. Si l’algorithme se termine pour la valeur n−1 alors il se termine aussi pour la valeur n est exécutant retourner. N’oubliez pas qu’un utilisateur peut rentrer n’importe quoi comme puissance(2, – 5) donc il faut bien vérifier sa terminaison.

somme ne se termine pas lorsque n est strictement positif. En effet, l’algorithme pour n se termine seulement si l’algorithme se termine pour n+1. Or, il n’existe pas d’entier strictement positif pour lesquels l’agorithme s’arrête.

Exercice 5

a – On souhaite écrire une fonction récursive qui calcule le carré d’un entier. Pour cela il va falloir se servir d’une relation entre carre(n) et carre(n-1) sachant que carre(1)=1. Représenter la pile d’appels pour carre(5).

b – Les combinaisons sont un concept de mathématiques décrivant les différentes façons de choisir un nombre donné d’objets dans un ensemble de taille donnée. Par exemple combien il est possible de tirer 6 boules de Loto sur 60 dans le moulinet. Ou de piocher 3 cartes dans un jeu de tarot. La combinaison de choisir p éléments parmi n éléments se notent C(p,n)=(n/p)*C(p-1, n-1). On a aurri C(0,n)=1 et C(n,n)=1. 

Ecrire la fonction récursive non terminale puis la fonction récursive terminale, et montrer la pile d’appels pour C(3,7). Via la fonction terminale, en déduire la fonction itérative.

c – Pour les combinaisons, on préfère généralement éviter la méthode du b car les divisions peuvent créer des problèmes d’arrondis. On va plutôt se servir de la relation suivante : C(p,n)=C(p,n-1)+C(p-1, n-1). Ecrire la fonction récursive et la pile ou arbre d’appels pour C(2,4).

a – Pour trouver un lien entre carre(n) et carre(n-1), on utilise la formule : (n+ 1)² = n² + 2n+ 1. On l’écrit en fonction de n vers n-1 : n² = (n−1)²+2(n−1)+1 d’où carre(n)=carre(n-1)+2*n-1. Le tour est joué !

algorithme récursif carré

La pile d’appels est :

algorithme récursif carré

b – Tout est dit dans l’énoncé, il ne reste qu’à l’écrire.

algorithme récursif combinaison

Voici la liste d’appels pour C(3,7) :

algorithme récursif combinaison

Et maintenant pour la version terminale, c’est un peu plus compliqué car il faut se questionner sur ce qu’on doit garder en mémoire pour la récursion. A chaque itération on a fait n/p fois le précédent, donc n/p * (n-1)/(p-1). On aurait pu l’écrire n(n-1)/p(p-1). Donc on pourrait stocker d’un côté la multiplication de n décroissant et de l’autre de p décroissant.

algorithme récursif combinaison

Voici la pile d’appels pour C(3,7,1,1) :

algorithme récursif combinaison

On déduit de la fonction terminale la fonction itérative. Il suffit de faire un Tant Que la condition d’arrêt n’est pas atteinte.

algorithme récursif combinaison

c – On a déjà la relation récursive dans l’énoncé.

algorithme récursif combinaison

Voici l’arbre d’appels pour C(2,4) :

algorithme récursif combinaison

Exercice 6

On définit la fonction de McCarthy comme suivant :

algorithme de mccarthy

Que fait la fonction pour n>100 ? pour n=98, 99, 100 ? En général pour n<=100 ?

On va faire un peu de mathématique… Si n > 100 on aura n-10. Le problème se pose quand on commence avec n<=100. Calculer pour 98, 99 et 100. On va faire une démonstration directe.

Pour n entre 90 et 100 compris – soit 11 valeur consécutive, ça nous servira plus tard. On fera Carthy(Carthy(n+11)) donc on dépassera la valeur de 100. Donc on aura Carthy(n+1) au final. Si n+1 n’est toujours pas supérieur à 100, on remet le couvert. Donc on s’arrête quand on passera de 100 à 101, or Carthy(101)=101-10=91.

En reprend ce qu’on a laissé au début du précédent paragraphe. Sur les 11 dernières valeurs consécutives, on aura un résultat de 91. On note que tout nombre entre 0 et 89, auquel on rajoute 11 tant que c’est inférieur à 90 aura une valeur finale entre 90 et 100 compris.

On en déduit que Carthy sur une valeur de 100 ou moins donnera la valeur de 91.

Il fallait bien un peu de mathématique. L’informatique n’est qu’une autre façon syntaxique de faire des maths !

Exercice 7

On parle de récursivité croisée lorsque deux fonctions s’appellent l’une l’autre récursivement.

On va tester sur une récursivité croisée pour savoir si un nombre est pair (vrai) ou impair (faux). Voici la proposition :

algorithme récursif croisé

Testez pour pair(2), impair(3), pair(3) et impair(2). L’algorithme est-il correct ? Sinon le changer pour vérifier la correction ← P.S: si le prof demande ça c’est que l’algo a un problème CQFD

Evidemment l’algo n’est pas correct. Prenons pair(3) → impair(2) → pair(1) → impair(0) → pair(-1) → impair(-2) → etc. C’est que les conditions d’arrêts ne marchent que si le nombre de la méthode pair est pair et la méthode impair est impair. On va seulement changer la méthode impair.

récursivité croisée pair impair

A vous de retester si c’est correct maintenant !

Exercice 8

Il est impossible de conclure sur le récursif sans parler des fameuses Tours de Hanoï (la hantise des étudiants et parfois aussi des chargés de TD et prof !). On va donc s’y prendre doucement.

tours de hanoi

On dispose de n plateaux de taille différentes, et de 3 tiges, numérotées de 0 à 2.

Initialement, tous les plateaux sont situés sur la tige i. Le but est de les transférer sur la tige j, en respectant les règles suivantes :

– On ne peux déplacer qu’un plateau à la fois.

– Les plateaux doivent toujours rangés par taille décroissante sur une tige (le plus grand en bas puis par ordre décroissant en remontant sur la tige).

1 – Résolvez le problème à la main si n = 2, i = 0 et j = 2 (donc 2 plateaux, ils sont tous de base sur la tige 0 et on veut les mettre sur la tige 2).

2 – Résolvez le problème à la main si n = 3, i = 0 et j = 2 (donc 3 plateaux, ils sont tous de base sur la tige 0 et on veut les mettre sur la tige 2).

3 – Supposez qu’un de vos amis sache résoudre le problème pour un certain n, et n’importe quels i et j. On vous demande de résoudre le problème pour n + 1. Vous avez le droit d’utiliser l’aide de votre ami. Comment vous y prenez-vous ?

4 – Ecrire la fonction récursive qui permet de résoudre ce problème pour tous n, i, j (Si vous y arrivez sans tricher félicitation ! Sinon c’est normal on est presque tous passé par ce grand moment d’incompréhension et de remise en cause de sa carrière…)

1 – 

On transfère le petit plateau de 0 à 1. 

On transfère le grand plateau de 0 à 2. 

On transfère le petit plateau de 1 à 2.

2 –

On transfère le petit plateau de 0 à 2. 

On transfère le plateau moyen de 0 à 1.

On transfère le petit plateau de 2 à 1. (on a déplacé 2 plateaux de 0 vers 1). 

On transfère le grand plateau de 0 à 2. 

On transfère le petit plateau de 1 à 0. 

On transfère le plateau moyen de 1 à 2. 

On transfère le petit plateau de 0 à 2. (on a déplacé 2 plateaux de 1 vers 2).

3 –

On déplacer n plateaux de i à l’emplacement qui n’est ni i ni j (par les séries de trois manipulations du point 2). On déplace ensuite le dernier plateau (le plus gros) de i à j. On remet à contribution l’ami pour déplacer les n plateaux vers j. 

4 –

Si vous trouvez ça… champagne ! On va renommé pour plus de facilité les tiges en d pour celle de départ, a pour celle d’arrivé et r pour celle qui reste

tours de hanoi

Exercice 9

Écrivez un programme pour trouver le PGCD de deux nombres en utilisant la récursivité.

Voici l’idée derrière l’algorithme :

pgcd algorithme

pgcd algorithme

Exercice 10

Écrivez un programme pour convertir un nombre décimal en binaire en utilisant la récursivité.

Voici l’idée derrière l’algorithme :

algorithme binaire

algorithme récursif binaire

Exercice 11

Écrivez un programme pour trouver le LCM de deux nombres en utilisant la récursivité.

LCM

En voici l’algorithme :

LCM

Exercice 12

Écrivez un programme pour vérifier si une chaîne donnée est Palindrome ou non.

Exercice 13

Le nombre Pi peut être calculé par la formule suivante :

pi récursif

Ecrire un algorithme récursif permettant de calculer la valeur de Pi en considérant la séquence jusqu’au rang n.

Faire de même avec les approximations de Pi suivants.

Série de Gregory-Leibniz :

Exercices corrigés algorithme récursif algorithme récursif

Et les séries plus anciennes de Madhava, Ramanujan, David et Chudnovsky (la factorielle sera un appel récursif à part entière) :

pi récursif

 

Voici l’algorithme en récursif :

pi récursif

Les autres formules suivent le même principe, inutile de tout détailler. Attention tout de même à utiliser le bon calcul dans la récursion ! (les algorithmes seront plus facile à écrire en récursif non terminal.

Exercice 14

Dans les années 1920, Wilhelm Ackermann et Gabriel Sudan, alors étudiants sous la direction de David Hilbert, étudient les fondements de la calculabilité. Sudan est le premier à donner un exemple de fonction récursive mais non récursive primitive, appelée alors fonction de Sudan. Peu après et indépendamment, en 1928, Ackermann publie son propre exemple de fonction récursive mais non récursive primitive. À l’origine, Ackermann considère une fonction ϕ(m, n, p) dépendante de trois variables.

Une fonction de seulement deux variables est donnée plus tard par Rózsa Péter et Raphael Robinson ; c’est cette dernière qui est connue aujourd’hui sous le nom de fonction d’Ackermann.

La fonction d’Ackermann-Péter est définie récursivement comme suit :

ackermann

La fonction grandit tellement vite qu’il est rapidement impossible de l’écrire avec un nombre classique et qu’il faut utiliser la notation de Knuth !

ackermann

La solution est très simple, mais je vous déconseille de lancer l’algorithme sur un PC.

ackermann récursif

Exercice 15

Voici la fonction de Sudan, autre élève de David Hilbert. Cette fonction a été conçu en 1927 donc une année plus tôt que la fonction d’Ackermann.

sudan récursif

Ici, plus la valeur de n grandit, plus le résultat de la fonction de la fonction explose. En voici l’example pour F_1(14,14).

sudan récursif

Rien de bien compliqué, il suffit de recopier la formule mathématique sous forme de récursion.

sudan récursif

Exercice 16

La fonction de Takeuchi, abrégée tak ou parfois tarai, est la présentation récursive d’une fonction qui doit son nom à Ikuo Takeuchi (竹内郁雄). La présentation de la fonction, qui, par ailleurs, admet une définition non récursive assez simple, peut requérir des calculs très longs si le compilateur qui l’implante n’est pas performant. Pour cette raison, elle est souvent utilisée pour tester les performances de l’implantation des fonctions récursives par le compilateur d’un langage de programmation.

takeuchi

La définition originale de Takeuchi était la suivante :

takeuchi

tarai est l’abréviation de « passer autour » en japonais. John McCarthy a nommé cette fonction tak() d’après Takeuchi.

La récursivité à été amélioré grâce à une récursivité croisée :

takeuchi

Exercice 17

La séquence Male-Female Hofstadter est définie par :

F(0)=1, M(0)=0 et

hofstadter

Ecrire un algorithme récursif permettant de calculer la séquence de Hofstadter.

Il s’agit d’un algorithme récursif croisé (aussi dit parfait récursif mutuel).

hofstadter récursion mutuelle

Exercice 18

Certains langages de programmation permettent la mémoïsation. Il s’agit d’une mise en cache des valeurs de retour d’une fonction selon ses valeurs d’entrée. Le but de cette technique d’optimisation de code est de diminuer le temps d’exécution d’un programme informatique en mémorisant les valeurs retournées par une fonction.

Ainsi, en réalisant la suite de Fibonacci, il est possible de se mémoriser les valeurs déjà calculées afin d’éviter de saturer la mémoire avec des valeurs déjà obtenu dans une autre branche de l’arbre d’appel.

En fait, chaque fois que nous calculons fib (i), nous pourrions simplement mettre en cache ce résultat et l’utiliser plus tard. Ainsi, lorsque nous appelons fib (n), nous ne devrions pas avoir à faire beaucoup plus que 0 (n) appels, car il n’y a que O(n) valeurs possibles que nous pouvons lancer sur fib(n).

Fibonacci memoization

Exercice 19

Certains langages de programmation permettent la mémoïsation. Il s’agit d’une mise en cache des valeurs de retour d’une fonction selon ses valeurs d’entrée. Le but de cette technique d’optimisation de code est de diminuer le temps d’exécution d’un programme informatique en mémorisant les valeurs retournées par une fonction.

Ecrire un algorithme calculant factoriel n (n!) utilisant le principe de mémoïsation.

Nous allons stocker chaque valeur de la factoriel dans un tableau :

factoriel mémoïsation

La deuxième solution est plus technique car cela demande d’avoir accès à la mémoire du cache avec par exemple l’import de lru_cache. Ainsi, le calcul de factoriel de grand nombre devient rapide et peu gourmand en mémoire.

Exercice 20

Et voici un petit exercice mêlant tout ce que vous avez pu voir récursivité, croisé et mémoïsation.

Il y a n oranges dans la cuisine et vous avez décidé de manger quelques-unes de ces oranges tous les jours comme suit :

  • Mangez une orange.
  • Si le nombre d’oranges restantes n est divisible par 2 alors vous pouvez manger n/2 oranges.
  • Si le nombre d’oranges restantes n est divisible par 3 alors vous pouvez manger 2*(n/3) oranges.

Vous ne pouvez choisir qu’une seule des actions par jour.

Étant donné l’entier n, renvoie le nombre minimum de jours pour manger n oranges.

Entrée : n = 10
Sortie : 4

Explication : Vous avez 10 oranges.

Jour 1 : Mangez 1 orange, 10 – 1 = 9.
Jour 2 : Mange 6 oranges, 9 – 2*(9/3) = 9 – 6 = 3. (Puisque 9 est divisible par 3)
Jour 3 : Mange 2 oranges, 3 – 2*(3/3) = 3 – 2 = 1.
Jour 4 : Mangez la dernière orange 1 – 1 = 0.

Il faut au moins 4 jours pour manger les 10 oranges.

Partager