Listes et pseudo listes en javascript.

Nous avons vu qu'un tableau en javascript a une longueur variable et qu'il existe des fonctions pour retirer le dernier élément du tableau ( pop) ou le premier élément (unshift). Nous avons choisi d'utiliser plus souvent pop car cette fonction ne fait que diminuer la taille du tableau sans avoir à re-numéroter chaque élément du tableau, comme l'aurait imposé un shift.
On peut donc considérer qu'un tableau se comporte comme une liste....
Mais qu'est-ce qu'une liste ? : C'est une collection d'éléments qui s'empilent les uns dernières les autres et dont ont peut en enlever qu'un seul à la fois. C'est donc une pile, à l'image d'une pile d'assiettes, la dernière assiette empilée, sera la première assiette extraite (Last in, first out ) ou LIFO. L'autre variante de structure de données étant la file d'attente: le premier entré sera le premier sortie (First In, First Out) FIFO .Cette structure pourrait être obtenue à l'aide des fonctions shift/ unshift.

Traitement des listes:

Tester si un élément est présent dans une liste.

// Méthode récursive: 
function exists (liste, e){
 return (liste.length===0)? false: e===liste.pop() ||  exists(liste,e) ;
}
// Attention exists récursive consomme la liste !

Méthode itérative:

function exists (liste, e){
 for(var i=0; i< liste.length; i++) 
  if(liste[i]==e) return true ;
 return false;
}

Une façon élégante est d'utiliser apply (ou list-it du caml ) vu précédemment:

function apply(f, l, n){
    for(var i=0; i< l.length ; i++){  n= f( l[i], n );  }
    return n;
}
// ici on peut alors écrire: 
var exists = function(l,e){
    return apply( function(element, boolean){ return (element===e || boolean)  ; }, l,  false ) ;
};

Union de listes

Comment faire l'union de deux listes ? C'est à dire tous les éléments de deux listes, sans répéter les éléments présents dans l'une et l'autre des deux listes ?

//union [1;2;3;3;4] [2;3;4;5;5]  récursive : 

function union(l1,l2){
     if (l2.length ===0) return l1;
     var e = l2.pop();
     return exists(l1,e) ?  union(l1,l2): union(l1.push(e),l2);
}
union([1,2,3,4], [2,3,4,5,5]);  //[1, 2,  3, 4, 5]

Retrait d'un ou plusieurs éléments d'une liste

Comment retirer un élément d'une liste ?
Méthode récursive:

function retrait(l, e){
    if(l.length == 0) return [];
    var c = l.pop();
    if( e===c)  return l ;
        var lb=retrait(l,e);
        return lb.push(c) && lb; // lb.push(c) renvoie la longueur de la liste, donc on renvoi la liste. 
}
retrait([1,3,4,5],4);

retrait itératif: utilisation de la fonction splice:

function retrait(l,e){
    for(var i=0; i< l.length; i++){
        if(l[i]==e)
            l.splice(i,1);  // retire en position i la longueur l ;
    }
    return l;
}
retrait([1,2,3,4,5],3);//[1, 2, 4, 5]

Idem à l'aide de la fonctionnelle apply :

function retrait(liste, e) {
    return apply( 
        function(element, liste){ 
           return element===e ? liste:(liste.push(element) &&liste) ;
       }
     , liste , [] );
}
retrait([1,3,6,7] , 3) ; // [1,6,7]

Filtrer suivant un prédicat: sélectionner les éléments correspondant à un prédicat dans une liste.

// filtrer selon un prédicat en mode récursif: 
function filtre(pred,l){
  if( l.length ===0) return [];
    var e = l.pop();    
    if( !pred(l.pop()) ) 
        return filtre(pred,l);   
    var suite = filtre(pred,l); // recursion ici
    return suite.push(e) && suite;
}

filtre(function(e){ return e>3 ; },[2,3,4,3,5]) ;

Note sur la syntaxe liste.push(element) && liste .

Normalement liste.push renvoi la longueur de la nouvelle liste, ce qui semble plutôt inutile. D'où cette syntaxe javascript qui
permet de renvoyer la liste après concaténation.

Décomposition d'un entier

Aplatir une liste:

Parfois il est utile de réduire un tableau contenant soit des tableaux soit des éléments, par un tableau simple ne contenant que des éléments.

// Fonction flatten:
function flatten(a,r){
    if(a.length == 0) return r;
    var cur= a.shift();
    cur instanceof Array && flatten(cur,r) || r.push(cur) ;
    return flatten( a, r);
}
flatten([1,3,4,[5,6]],[]);
// En évitant d'initialiser le tableau à []:

Décomposition d'un entier:

Savez vous combien de façons existe-t-il d'écrire une addition dont le résultat est 5 ?
[11111], [1112],[1,2,2],[3,2],[11,3],[1,4],[5] : 7

D'une façon général, utilisez la récursion pour calculer le nombre de façons d'écrire un nombre ?

Indice :
Pour écrire une addition dont la somme est n, à l'aide d'un entier inférieur à q, on peut écrire alors
n = q +(n-q) ;
Il y aura donc (n-q) décompositions possibles pour écrire les décompositions dont au moins un élément est de valeur q et les autres de valeur inférieure à q.
On peut également dire que pour avoir toutes les décompositions de n avec des éléments dont la valeur est inférieure à q; il faut rajouter toutes les décompositions de n avec un élément de valeur q-1;

On peut donc écrire
toutesDec(n,q)= toutesDec(n,q-1)+ toutesDec(n-q,q) ;
Par ailleurs,

• il n'existe qu'une décomposition de n avec q=1


• 0 décompositions avec q<=0 ou n<0 ;


• On suppose également qu'il n'y a qu'une décomposition de n=0 avec q>0 correspondant au cas de la décomposition de n par lui meme; exemple ttes Dec(0,5) = 1 car cela correspond au cas ou= toutesDec(n-q,q) ou n=q ,

Réponse:

function toutesDec(n,q){
 if(n==0) return 1;
 if(n<=0 || q<=0) return 0;
 if(q==1) return 1;
 return  toutesDec(n,q-1)+toutesDec(n-q, q)  ;
}

toutesDec( 12,12) ; //77  

On peut aller plus loin en écrivant ces décompositions:
Attention ne lisez pas tout de suite la solution... c'est quand même pas super simple !
Un truc important js n'est pas typé, donc pensez type à chaque retour de valeur, dans ma solution, chaque valeur retournée correspond à un tableau de tableaux ou plutôt une liste de listes.

// instructions de débuggage:
function clear(){document.body.innerHTML="";}
function d(m){ document.body.innerHTML += '
'+m.toString()+'
' ;} 

function toutesDec(n,q){
        if(n&tl;q) return toutesDec(n,n);
        if(n <= 0 || q <= 0 ) return [[]];
 if(q==1){
            var r= [];
            for(var i=0; i < n;i++) r.push(1);
             return [r];
        }
        var suite = toutesDec(n-q, q)  ;
        var listeb = map(suite, function(sousliste){ sousliste.push(q); return sousliste;}) ;                
        var listea = toutesDec(n,q-1)  ; 
        return listea.concat(listeb);

}
dolist= function(l,f ){ for(var i in l){ f(l[i]);} };
dolist(toutesDec( 10,4),d);

A vous d'inventer des problèmes plus compliqués encore, cette fonction est appelée "petite fonction de Ramanujan"
grand mathématicien du début du 20ème siècle.

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.

Recursion suite: Algorithme d'Euclide et Tours de Hanoi

Algorithme d'Euclide:

L'algorithme d' Euclide permet de déterminer le pgcd de la manière suivante:
- pgcd(a, a) = a,
- pgcd(a, b) = pgcd(a − b, b) si a > b ou pgcd(a, b − a) si a

Programmez l'algorithme d'Euclide de façon récursive.
Nota bene une autre méthode pour calculer l'algorithme d'Euclide est l'opérateur modulo "%"
pgcd (a,b) = b si a%b == 0 , ou sinon (a%b) % b ;

function pgcd(a,b){
 return  a>b && pgcd(a-b, b)|| a<b && pgcd(a,b-a) || a===b && a ; 
}
//Et avec l'opérateur modulo :
function pgcd(a,b){      
   return  a>b && a%b>0 && pgcd(b,a%b) || (b>a)&& pgcd(b,a) || a%b===0 && b ;
}
pgcd(2736,486144);//30

Ici on utilise volontairement les expressions javascripts pour raccourcir l'écriture, ce qui n'est pas forcément toujours à conseiller. Pour les matheux, un problème plus complexe est de calculer les coefficients de Bezout, Ces coefficients sont très utiles dans le cryptage des données.

Tours de Hanoi :

Voici (enfin) l'incontournable problème qui illustre la récursivité, ce problème a été inventé au début du siècle par un mathématicien français afin d'illustrer la résolution d'un problème par récursivité.
Attention, essayez de comprendre ce problème et sa solution... c'est un problème fondamental, il vous permettra de comprendre les autres solutions par récurrence même si vous avez étudié la récurrence dans vos études !
Dans un temple bouddhiste, à Hanoi 3 mâts sont disposés en ligne l'un à côté de l'autre. Sur le mât de gauche sont empilés des disques d'or très lourds, percés au centre, de diamètre variable, et ordonnés du plus grand au plus petit.
Un moine est chargé de transférer ces disques sur le troisième piquet à droite, avec cependant un impératif: il ne doit jamais déposer un disque d'un diamètre supérieur aux disques précédents sur un mât donné.
La légende dit que la fin du monde surviendra lorsque le moine aura terminé son travail...
Pouvez vous programmer un mode d'emploi pour aider notre moine dans sa tache interminable ? Il faut écrire un programme qui donne
hanoi( ndisques, "gauche", "droite", "milieu")
qui permet à notre moine de savoir de transférer ndisques de gauche à droite, en s'aidant du mât du milieu .

Réponse:
Le principe de récurrence dit que si vous pouvez le faire pour 1 élément et si vous savez passer de l'élément n à n-1 alors vous savez résoudre le problème ! ....
Ainsi on suppose que vous savez passer une colonne de n-1 disques de gauche au milieu ou à droite.. comment passer une colonne de n disques de gauche à droite :
passer une colonne entière de n-1 disques de gauche au milieu, // vous prétendez que vous savez le faire
passer le disque large de la base de gauche à droite // vous savez le faire pour de bon !
puis repasser la colonne de n-1 disques du milieu à gauche... // vous prétendez savoir le faire

var r=[];  // le résultat sera dans un tableau .
function hanoi (n,g,d,m){
    if(n==0) return r ;
    hanoi(n-1, g,m,d);
    r.push( "Faire passer le disque de " + g  + " à   " + d );
    hanoi(n-1,m,d,g) ;
 }
hanoi(10,'Gauche', 'Droite', 'Milieu') ;
r ;

Le programme des tours de Hanoi, n'est pas un simple jeu ni un puzzle, c'est l'illustration même de la récursivité. Votre travail ici est de passer de n disques à n-1 disques , d'une part et d'autre part de savoir quand cela doit s'arrêter, ici lorsqu'il n'y a plus de disque à déplacer. C'est tout .
Prenez donc le temps de comprendre ce programme il vous permettra de comprendre la magie de la récursion. C'est particulièrement utiles dans les programmes du type anagrammes ou comptage des parties d'un ensemble.

Des exercices !

Le mieux pour apprendre les particularités d'un langage c'est de s'exercer, voici quelques exercices d'algorithmique qui permettront de se familiariser avec la programmation fonctionnelle et récursive en javascript.

Calculer de la dérivée d'une fonction f en un point x à l'aide de l'approximation dx.
On pourra écrire: dérivée( f, x, dx).

var dérivée= function(f,x,dx){
  return (f(x+dx)-f(x))/dx ;

var carré = function(x){ return x*x ;}
dérivée(carré,30,0.0000001); ///f'(x^2)=2x  (réponse 60)

Version 2 : renvoyer la fonction dérivée :

var dérivée =function(f,dx){
return function(x){ (f(x+dx)-f(x))/dx} ;
}

Avez vous remarqué qu'ici on renvoi non pas un nombre mais une fonction ?,

dérivée(carré, 0.001)(3);

Ou encore :

var dérivée = function(dx){
       return function(f){
               return function(x){ 
                    return (f(x+dx)-f(x))/dx} ;
         }
}

// n'oubliez pas les return !!

Dans cette dernière version on peut parler de "curryfication", terme utilisé en hommage à Haskell Curry précurseur avec Alonzon Church du lambda calcul, et qui avait montré cette possibilité , l'opérateur () ne se prête pas tellement à une curryfication systématique des fonctions comme en Caml mais il est souvent intéressant cependant de renvoyer une fonction en résultat.

On peut ainsi écrire:

var fprime = function(f){ return dérivée(0.001)(f) ; }
var sinprime = fprime(Math.sin) ;
var cosprime = fprime(Math.cos) ; 
var carreprime = fprime(function(x){return x*x;}) ;

Pour être utilisé ultérieurement :

sinprime(Math.PI) ;// 0.99 

Récursion :

La récursion est très peu utilisée par les programmeurs java ou C, souvent à raison car ces programmes sont fondamentalement procéduraux. Par contre le javascript se prête très bien à la programmation récursive, et la récursion permet de traiter des problèmes avec souvent beaucoup plus de facilité que le traitement procédural, il faudra par contre faire attention à ne pas compromettre la puissance de la machine par des récursions imbriquées.

On s'échauffe avec ce petit problème :
Créer une fonction récursive qui calcule le nombre de chiffres d'un entier :

function nchiffres(n) { 
  return n<10&&1 || 1+ nchiffres( Math.floor(n/10) )  ; 
}  

Remarquez la syntaxe qui permet de s'affranchir du if/else et qui n'est à pas nécessairement à considérer comme un exemple de programmation à suivre!