Javascript récursif, suite

Suite de Fibonacci:

La suite de fibonacci a été étudiée par le grand Léonard de Vinci... est définie ainsi:

f(0) = 0 , f(1)= 1  et f( et  f(n)= f(n-1)+f(n-2) ;

Programmez cette suite..
Vous avez probablement écrit l'algorithme naïf:

function fibo(n){ return (n<2) ? n : (fibo(n-1)+ fibo(n-2)); }
fibo(10);

Or cet algorithme recalcule à chaque fois fibo et ne met pas en mémoire les résultats précédents: une solution plus efficace consiste garder en mémoire les deux précédents résultats et de les échanger à l'aide des arguments d'appel de la fonction:

// avec une cloture:
function fib(n){
    if(n<=1) return n;
    function f(p , pp){
        n--;
        return (n==0)? pp : f(p+pp, p);
     }
    return f(1,1);
}

ou encore:

function fib(n){
    function f(p ,pp,n){
        return (n<=2)? p :f(p+pp, p ,--n);
     }
    return f(1,1,n);
}
//ici la récursion utilise les arguments pour obtenir le résultat final, 
// et n est incrémenté à la façon d'une boucle for.

Les accros du récursif pourront peut-être écrire:

function fibo(n){
    var f0=0, f1=1 , f ;
    if(n<2) return n ;
    for(i=2 ; i  <= n ; i++){
        f=f1 +f0 ;
        f0 =f1 ;
        f1 =f ;
    }
    return f;
}

fibo(10);

Programmation dynamique et clôture en javascript

Douglas Crockford propose dans son livre une version utilisant la programmation dynamique avec un tableau dans une "cloture" (en anglais "closure"), il nomme cette technique la "memoization"...

// Le but: f(0) = 0 , f(1)= 1  et f(n)= f(n-1)+f(n-2) ;

var fibodougcrock = function(){
   var memo =[0,1] ; // variable cloturée = inaccessible hors de la fonction.
   var fibo = function(n){
                      if(n<2) return n ;
                      if(memo[n]) return memo[n];
                      memo[n]= fibo(n-1) + fibo(n-2) ;
                      return memo[n] ;
   }
   return fibo ;
}

var myFibo = fibodougcrock() ;
myFibo(20); 

L'intérêt de cette dernière version est son caractère dynamique les calculs précédents sont mis en mémoire, de façon à ne faire qu'une fois le calcul pour chaque n. Cela coûte un peu de mémoire mais rend le calcul possible.
Par ailleurs, le tableau memo est une variable cloturée ( closure en anglais), cette variable ne peut être modifiée que par la fonction elle même, elle n'est pas atteignable par le code javascript, elle est donc protégée et isolée dans sa fonction. Mais, d'autre part, elle réserve la mémoire pour le tableau mémo dans son enclos, qui ne sera pas libérée tant qu'il y aura des références à fibodougcrock dans le programme.
Les clôtures sont intéressantes en javascript car elles permettent l'encapsulation des données, notion si chère aux programmeurs objets. Mais elles sont aussi dangereuses, car il est possible de créer des clôtures sans le savoir avec une fuite de mémoire...Il est donc plus important de les reconnaître que de les utiliser.