7. Récursivité

On appelle fonction récursive une fonction qui s’appelle elle-même. Ceci est très lié à la notion de récurrence en mathématiques.

Par exemple, la factorielle en mathématiques est définie par la condition intiale \(0! = 1\) et par la relation de récurrence \(n! = n\cdot(n-1)!\) lorsque \(n\geq1\).

In [1]: def factorielle(n):
   ...:     return 1 if n==0 else n*factorielle(n-1)
   ...: 

In [2]: factorielle(3)
Out[2]: 6

Par exemple lors de l’appel de factorielle(3)

• 3*factorielle(2)

• 2*factorielle(1)

• 1*factorielle(0)

A noter que le case de base doit être impérativement défini sinon l’algorithme ne termine pas. En Python, il existe un garde-fou consistant à imposer un niveau maximum de récursion. Si jamais celui-ci est dépassé, une exception est levée.

À faire

baratin sur la tour de Hanoï

Once Loop Reflect