On rappelle que factorielle de n (notée ) est définie ainsi:
Par exemple:
factorielle
qui prend un paramètre n
entier en entrée et qui renvoie le factoriel de n
en sortie.factorielle_rec
.La suite de Fibonacci est une suite de nombres entiers définie par récurrence.
Les deux premiers termes sont 0 et 1, puis un terme est la somme des deux termes précédents.
On obtient ainsi les nombres dits de Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21…
La définition mathématique est:
fibo
qui calcule le terme
de la suite de Fibonacci. Par exemple: fibo(7)
renvoie 13.fibo_iter
.La fonction est_pair
définie ci-dessous indique si un entier naturel est pair ou non.
def est_pair(n):
while n > 0:
n = n - 2
return n == 0
Écrire une version récursive de cette fonction est_pair_rec
.
NSI Terminale de Serge Bays aux éditions Eyrolles
On autorise seulement deux opérations sur les entiers:
La fonction somme
définie ci-dessous renvoie la somme de deux entiers positifs avec ces deux opérations.
def somme(a, b):
while b > 0:
a = a + 1
b = b - 1
return a
somme_rec
.somme
et somme_rec
afin de pouvoir renvoyer la somme de deux entiers quelconques.NSI Terminale de Serge Bays aux éditions Eyrolles
somme_list_rec(tab:list, somme=0) -> int:
qui prend un paramètre une liste de nombres et renvoie la somme des termes de cette liste. Par exemple: somme_list_rec([4, 7, 2])
renvoie 13
.somme_list_rec([4, 7, 2])
. On pourra s’aider du site http://pythontutor.com/.NSI Terminale de Serge Bays aux éditions Eyrolles
Écrire une fonction récursive avec accumulateur inverse(txt:str, inv="") -> str:
qui prend en paramètre une chaîne de caractères txt
et qui renvoie la chaîne en inversant l’ordre des lettres. Par exemple: inverse("azerty")
renvoie ytreza
.
Le calcul des nombres de Fibonacci est rendu beaucoup plus efficace en utilisant des accumulateurs qui retiennent les valeurs des deux termes précédents afin d’éviter de les recalculer.
Compléter le code ci-dessous pour mettre en pratique cette technique.
def fib_acc(n, f0=0, f1=1):
# cas de base
if n == 0:
return ...
elif n == 1:
return ...
# appel récursif
return ...
Comparer l’efficacité de ces deux algorithmes en calculant un terme de rang assez élevé.
Chronométrer ces deux algorithmes grâce à la méthode time.time