"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>o.
0
u
9.7 • Récursivité
On peut remarquer que, pour tout réel x et tout entier n ::=::: 1, on a X1=xxn1 • Écrivons une seconde fonction puissanceR(x,n) renvoyant le nombre X1, utilisant la
relation puissanceR(x,n)=x*puissanceR(x,n- 1) :
Fonction puissanceR(x: réel, n: entier) : réel
Rôle : calcul récursif de xn
Début
Si n==O Alors
1
Retourner(l)
Sinon
1
Retourner(x ~' puissance(x,n-1 ))
FinSi
Fin Fonction
Une telle fonction fait appel à elle-même, on dit qu'il s'agit d'une fonction
récursive.
~ Une fonction récursive est une fonction s'appelant elle-même. Plus généralet.:J ment, un algorithme récursif est un algorithme s'appelant lui-même.
:<:;
.,,
c::
:l
~
"
~
0
:;
"' c::
0
c::
c::
.9
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
Lorsqu'on souhaite écrire une fonction u(n) retournant le terme un d'une suite
(un), si cette suite est définie par récurrence, il est alors plus commode de passer par
une fonction résursive. Cependant, son exécution peut dans certains cas, s'avérer
être beaucoup plus lente que si cette fonction avait été construite de manière
itérative.
Exemples
La suite de Fibonacci est la suite (un) définie par u 0 = u 1 = 1 et pour tout entier
n ~ 2 par un= un-t + un_ 2 . La fonction récursive fib(n) suivante, écrite en Python,
renvoie un à tout entier naturel n :
def fib ( n ):
i f n <= 1:
r e turn(I)
el s e :
r et urn (f i b(n- l )+fi b ( n-2) )
L'appel de fib(S) renvoie 8 quasi instantanément, alors que l'on obtient la valeur
de fib(35) en 22 secondes environ, et un temps encore plus long lorsque n
augmente. On résout ce problème avec la fonction itérative fibl(n) suivante :
def fi bl ( n ):
a , b=l , 1
i f n > 1 :
for k i n r ange( l , n ) :
b=a+b
a = b - a
r e turn(b)
209