Calcul récursif des nombres de Fibonacci

On remarquera que ce petit programme récursif présente une programmation identique à sa définition mathématique. C'est là l'élégance et la concision des définitions récursives. Contrairement à un programme itératif, il n'y a pas de boucle conduisant à la valeur du rang n recherché. C'est l'ordinateur qui fait le boulot !.. :

Tant que n n'est ni 0 ni 1, le programme décrémente n et empile les f(k) non évalués pour k = n, n - 1, ...,2 (récursion). Connaissant fibo(0) = fibo(1) = 1 (condition d'arrêt), on remonte à f(2) = 1 + 1 = 2, puis f(3) = 2 + 1 = 3, etc.

<SCRIPT LANGUAGE=JavaScript>
function fibo()
{
n=10;n=eval(prompt("fibo(n), donnez n : ",n))
alert("fibo("+n+") = "+fibo(n))
}

function fibo(n)
{
if (n >=2) {return fibo(n - 1) + fibo(n - 2)}
else
{
if (n==0 || n==1) {return 1}
}}
</SCRIPT>

! fibo(40) est calculé sans problème mais fibo(50) inquiète déjà le navigateur ! ça commence à faire beaucoup de lapins... : c'est le problème général des programmes récursifs devant "empiler" en mémoire les résultats intermédiaires en attente d'évaluation. Un petit programme itératif est finalement plus efficace.