La clé unique

Fonctions reccursives

April 30, 2021

Définition

Une fonction récursive est une fonction qui s’appelle elle-même.

Pour compter à rebours à partir de 10, il suffit de :

• afficher 10

• compter à rebours à partir de 9.

Pour compter à rebours à partir de 9, il suffit de :

• afficher 9

• compter à rebours à partir de 8.

...et ainsi de suite. Autrement dit, pour compter à rebours à partir d’un entier positif n quelconque,

il suffit de :

• afficher n

• compter à rebours à partir de n-1.

On peut donc programmer une fonction qui explique comment compter à rebours... en utilisant

le fait de savoir compter à rebours. Il faut juste ne pas poursuivre une fois à 0.

En fait, pour compter à rebours à partir de 0, il faut juste :

• afficher 0

Voici ce que cela donne en Python :

[ ]: def compteAR(n):

print(n)

if n>0:

compteAR(n-1)

! Testez cette fonction pour n=10.

[ ]: #test

compteAR(10)

1

1 Exercice 1

!Complétez le programme ci-dessous pour qu’il permette de demander un pseudo à l’utilisateur

jusqu’à ce que ce dernier propose un pseudo de longueur supérieure à 4 :

[ ]: def demandePseudo():

print("Choisis-toi un pseudo de plus de 4 symboles.")

pseudo = input()

if len(pseudo) ... : #compléter le test

print("C'est bon. Ton pseudo est :", pseudo)

else:

... #il n'y a plus qu'à rappeler la fonction

#test

demandePseudo()

!Complétez le programme ci-dessous pour qu’il permette de demander un pseudo à l’utilisateur

jusqu’à ce que ce dernier propose un pseudo de longueur supérieure à 4, sans utiliser de récursivité.

[ ]: def demandePseudo2():

print("Choisis-toi un pseudo de plus de 4 symboles.")

pseudo = input()

while len(pseudo) ... :

print("C'est bon. Ton pseudo est :", pseudo)

#test

demandePseudo2()

On appelle une fonction qui n’utilise pas la récursivité une fonction explicite.

Les boucles while permettent de transformer une fonction récursive en fonction explicite, mais

cela donne souvent un code plus lourd.

2 Exercice 2

Une foule doit quitter un lieu de festival à l’aide de cars de 49 places chaque.

On veut savoir combien de personnes prendront le dernier car si tous les cars sont remplis.

Une solution explicite consiste à faire la division du nombre de personnes par 49 et considérer le

reste.

Une solution récursive consiste à dire que pour résoudre ce problème il suffit de remplir un car,

puis de résoudre le problème pour les gens qui restent.

!Programmez une fonction récursive combienRestent(nb) qui prend en entrée un entier positif

2

nb, le nombre de personnes qui attendent de monter dans les cars, qui renvoie le nombre de

passagers du dernier car.

[ ]: def combienRestent(nb):

if nb>49:

return combienRestent(...)

else:

return ...

! Effectuez des tests pour obtenir les résultats suivants :

>>> combienRestent(50)

1

>>>

...