TD 3
TD 3
TD 3
Fonctions récursives
Programmation et Algorithmique
Exercice
Exercice
La suite de Syracuse est une suite dénie de la façon suivante :
u
n
si un est pair
2
u0 ∈ N∗ , et ∀n ∈ N, un+1 =
si un est impair
3un + 1
Programmation et Algorithmique
Fonctions récursives
Exercice
La factorielle d'un nombre n, notée n!, est dénie par :
n! = 1 × 2 × 3 × . . . × n
Programmation et Algorithmique
Fonctions récursives
Dénition
On dit qu'une fonction ou une procédure est récursive si elle
s'appelle elle même.
Exemple
Que renvoie cet algorithme ?
début
Function calcul(n)
si n mod 2 = 0 alors
n←calcul(n/2)
fsi
retourne(n)
End Function
acher(calcul(7))
acher(calcul(12))
acher(calcul(16))
n
Programmation et Algorithmique
Fonctions récursives
Dénition
On dit qu'une fonction ou une procédure est récursive si elle
s'appelle elle même.
Exemple
Que renvoie cet algorithme ?
début
Function calcul(n)
n←calcul(n*2)
retourne(n)
End Function
acher(calcul(3))
n
Programmation et Algorithmique
Fonctions récursives
Exercice
La factorielle d'un nombre n, notée n!, est dénie par :
n! = 1 × 2 × 3 × . . . × n
Programmation et Algorithmique
Fonctions récursives
Exercice
La suite de Fibonacci (Fn )n∈N est dénie de la façon suivante :
Ses deux premiers termes sont F0 = 0 et F1 = 1 ;
Si n ⩾ 2, Fn = Fn−1 + Fn−2 .
Programmation et Algorithmique
Fonctions récursives
Exercice
On s'intéresse à des placements nancier. On dispose d'un montant
initial "val", que l'on place à un taux d'intérêt de "t"%, pendant
"n" années.
Programmation et Algorithmique
Fonctions récursives
Exercice
Dans ma maison, il y a un escalier de 17 marches.
Pour descendre cet escalier, je peux, à chaque pas, descendre de
une, deux ou trois marches.
Programmation et Algorithmique
Fonctions récursives
Exercice
On reprend le TP du démineur. On considère qu'on a écrit une
procédure "test", qui permet de dévoiler le nombre correspondant à
la case sélectionnée par l'utilisateur.
1. On veut créer une nouvelle procédure, "extension", qui est
appelée à la n de la procédure "test", et qui fait en sorte que si
l'utilisateur a trouvé un 0, les 8 cases voisines sont dévoilées aussi.
2. Comment faire pour que si parmi les 8 case voisines dévoilées, il
y a aussi un 0, les cases voisines de ce nouveau 0 soient elles aussi
dévoilées ?
Programmation et Algorithmique