Discussion :

[arwin]

Bonjour,
voici une fonction récursive qui rempli un tableau avec des chiffres allant de 1 à n.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
 
function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1); 
    countArray.push(n);
    return countArray;
  }
}
console.log(countup(5));

Je bloque dans la compréhension du fonctionnement de cette fonction. La ligne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

const countArray = countup(n - 1);

est censée appeler la fonction elle même avec comme paramètre n-1 donc on va au début de la fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
function countup(n-1) {
  if (n-1 < 1) {
    return [];
  } else

et on va tomber encore une fois sur la ligne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

const countArray = countup(n - 2);

qui nous fait remonter encore au début de la fonction et ainsi de suite jusqu'à n = 0 pour lequel la fonction retourne un tableau vide (et ne dépasse pas le else).

Du coup on ne pourra jamais atteindre la ligne d'après, à savoir

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

   countArray.push(n);

et donc on ne pourra rien "pusher" dans le tableau .... Parce que, et si mes connaissances sont correctes, lorsqu'on appelle une fonction on ne va plus exécuter le code qui se trouve après jusqu'à l'exécution complète de la fonction ....

J'ai l'impression d'avoir raté quelque chose de fondamental ? c'est grave docteur ?

[NoSmoking]

Bonjour,
pour t'aider à comprendre ce qui ce passe, pas toujours évident d'ailleurs, il faut que tu observes le cheminement et rien de tel que de mettre des console.log().

Essaie avec ce code et tu vas te rendre compte que tu as occulté quelque chose quand tu écris « Du coup on ne pourra jamais atteindre la ligne d'après, à savoir  ».

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
function countup(n) {
  if (n < 1) {
    console.log("end")
    return [];                           // création de l'array à remplir
  } else {
    console.log("else :", n)
    const countArray = countup(n - 1);   // ici on appelles la fonction avant d'exécuter ce qui suit 
    countArray.push(n);
    console.log(JSON.stringify(countArray));
    return countArray;
  }
}
console.log("Result : ", countup(5));

[arwin]

Merci NoSmoking.. ton idée est génial mais je n'arrive toujours pas à saisir le truc.
Après la ligne "end" le programme va retourner un tableau vide ... jusqu'à là c'est clair. Mais après il devrait sauter le else puisqu'on est dans le cas n=0 et donc on devrait sortir de la fonction et arriver à la ligne : console.log("Result : ", countup(5)); non ?
Je ne comprend pas comment on a obtenu la ligne : [1] et ce qui suit

[NoSmoking]

Mais après il devrait sauter le else puisqu'on est dans le cas n=0 et donc on devrait sortir de la fonction

tu oublies que la fonction s'auto appelle donc il y a un empilement puis un dépilement des appels.

Essaies de comprendre en regardant ce pseudo code, ne cherche pas à l'exécuter, il plantera, c'est juste pour visualiser les empilements dépilements

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
function countup(n)
  { // ce bloc est exécuté
    // ici n = 5
    if (n < 1) { // non exécutée
      console.log("end")
      return [];
    }
    else {
      const countArray = countup(n - 1)
      { // ce bloc est exécuté
        // ici n = 4
        if (n < 1) { // non exécutée
          return [];
        }
        else {
          const countArray = countup(n - 1)
          { // ce bloc est exécuté
            // ici n = 3
            if (n < 1) { // non exécutée
              return [];
            }
            else {
              const countArray = countup(n - 1)
              { // ce bloc est exécuté
                // ici n = 2
                if (n < 1) { // non exécutée
                  return [];
                }
                else {
                  const countArray = countup(n - 1)
                  { // ce bloc est exécuté
                    // ici n = 1
                    if (n < 1) { // non exécutée
                      return [];
                    }
                    else {
                      const countArray = countup(n - 1)
                      { // ce bloc est exécuté
                        // ici n = 0, on arrête tout
                        if (n < 1) {
                          return [];
                        }
                        else { // non exécutée
                          const countArray = countup(n - 1);
                          countArray.push(n);
                          return countArray;
                        }
                      };
                      // maintenant countArray = []
                      // l'exécution se poursuit avec n = 1
                      countArray.push(n);
                      // countArray = [1]
                      return countArray;
                    }
                  };
                  // l'exécution se poursuit avec n = 2
                  countArray.push(n);
                  // countArray = [1, 2]
                  return countArray;
                }
              };
              // l'exécution se poursuit avec n = 3
              countArray.push(n);
              // countArray = [1, 2, 3]
              return countArray;
            }
          }
          // l'exécution se poursuit avec n = 4
          countArray.push(n);
          // countArray = [1, 2, 3, 4]
          return countArray;
        }
      };
      // l'exécution se poursuit avec n = 5
      countArray.push(n);
      // countArray = [1, 2, 3, 4, 5]
      return countArray;
    }
  }
// l'exécution est terminée
console.log("Result : ", countup(5));

[arwin]

c'est bien de décortiquer le code, ca permet de voir où ça coince précisément et là du coup c'est à la ligne 50 : // l'exécution se poursuit avec n = 1 !!!!
comment et pourquoi ? on était à n = 0 non ?! ( ligne 39 // ici n = 0, on arrête tout). Est-ce que le cas n = 1 (2, 3 etc ..) a été gardé en mémoire quelque part ?

Parce que la limite qui reste floue dans ma tête c'est lorsqu'on arrive à n = 1,
on a alors : const countArray = countup(0);
On remonte alors au début de la fonction avant même de stocker quoi que ce soit dans countArray .... donc vraiment je ne vois pas comment ça se produit ce dépilement dont tu parle NoSmoking !!!!

[mathieu]

à la ligne 37 du code NoSmoking, il y a l'appel de "countup(n - 1)" avec n = 1.
donc à la ligne 50, on est dans même contexte donc il s'agit d'une variable n qui contient encore 1.

chaque appel de la fonction countup va créer une nouvelle variable n qui gardera sa valeur uniquement pendant l'exécution de cette fonction. et donc la valeur de cette variable est indépendante des autres variables n des autres appels même si c'est la même fonction.

[arwin]

Merci Mathieu ... je pense que tu n'as pas vu ce qu'ai rajouté à mon message ... pour le cas n=1 :

"
on a alors : const countArray = countup(0);
On remonte alors au début de la fonction avant même de stocker quoi que ce soit dans countArray
"
Donc il y a bien l'appel de la fonction countup(0) avant de pouvoir éventuellement exécuter le reste du code ?

Il y a vraiment quelque chose qui m'échappe là ...

et lorsque tu dis "chaque appel de la fonction countup va créer une nouvelle variable n qui gardera sa valeur uniquement pendant l'exécution de cette fonction. et donc la valeur de cette variable est indépendante des autres variables n des autres appels ..." .... pourquoi on commence par 1 puis 2 etc .... je ne vois pas bien cette histoire de pilement et de dépilement ? ça se passe où ? dans quel ordre ? à quel niveau ?

[mathieu]

cet empilement se fait dans le moteur javascript, c'est comme si le code lancé était le suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
console.log(countup_appelN1(1));
 
function countup_appelN1(n_appelN1) {
  if (n_appelN1 < 1) {
    return [];
  } else {
    const countArray_appelN1 = countup_appelN0(n_appelN1 - 1); 
    countArray_appelN1.push(n_appelN1);
    return countArray_appelN1;
  }
}
 
function countup_appelN0(n_appelN0) {
  if (n_appelN0 < 1) {
    return [];
  } else {
    const countArray_appelN0 = countup...(n_appelN0 - 1); 
    countArray_appelN0.push(n_appelN0);
    return countArray_appelN0;
  }
}

[arwin]

Donc, si je comprend bien, à chaque fois qu'on appelle countup(5); countup(4); countup(3); etc .. le moteur JS la stocke quelque part ... (stocke quoi en fait ? la valeur ? mais la valeur ne peut pas être calculée à ce stade !!! l'expression ?!!) et qu'une fois qu'on on arrive au 'base case' (dans notre cas n = 0), ce même moteur procède au dépilment en commençant par le dernier appel (chronologiquement parlant) de la fonction (c'est-à-dire countup(1)), puis countup(2) etc ... en la stockant dans le countArray et en procedant au push par la suite; ???

[NoSmoking]

le moteur JS la stocke quelque part

Contexte d'exécution et pile d'exécution, ou autres termes, voilà des mots qu'il te faut approcher si tu veux aller plus loin dans la compréhension.

Un petit schéma pour te montrer comment est exécutée ta récursivité


Tu trouveras plus d'info sur : Récursion et pile (en français)

[javatwister]

C'est sûr que c'est moins intuitif que ça

Code javascript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
function countup(n) {
	n.unshift(n[0]-1);
	return n[0]>1 ? countup(n) : n
}
console.log(countup([5]));

mais ça remue bien les neurones

[arwin]

Merci les gars ... ....

c'était pas évident mais les choses sont beaucoup plus claires maintenant.

Je poste un petit dessin qui pourrait aider d'autres personnes à comprendre plus facilement / plus rapidement le principe de la récursivité.

Super ton code javatwister ... et effectivement ca apprendra aux plus paresseux des neurones à danser et la java et le twist en même temps