Qu'est-ce que la récursivité ? Explication détaillée de la récursivité en javascript

Le contenu de cet article porte sur ce qu'est la récursivité ? L'explication détaillée de la récursivité en JavaScript a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'elle vous sera utile.

1. Qu'est-ce que la récursivité ?

Le concept de récursivité est très simple, "appelez-vous" (prenez une fonction comme exemple ci-dessous).

Avant d'analyser la récursivité, vous devez comprendre le concept de « pile d'appels » en JavaScript.

2. Push et pop

Qu'est-ce qu'une pile ? On peut comprendre qu'il s'agit d'une certaine zone de la mémoire. Cette zone est assimilée à une boîte. Si vous mettez quelque chose dans la boîte, cette action pousse la pile. Ainsi, la première chose à déposer est en bas de la boîte, et la dernière chose à déposer est en haut de la boîte. Sortir quelque chose de la boîte peut être compris comme *le pousser hors de la pile.

Nous arrivons donc à la conclusion que nous avons l'habitude de prendre les choses de haut en bas. La première chose à déposer est au fond de la boîte, et la dernière chose à récupérer.

En JavaScript, lorsqu'une fonction est appelée, le comportement de pile se produira. La pile (pop) ne se produira pas jusqu'à ce qu'une phrase contenant le mot-clé return soit rencontrée ou que l'exécution soit terminée.

Regardons un exemple. Quel est l'ordre d'exécution de ce code ?

function fn1() {
    return 'this is fn1'
}

function fn2() {
    fn3()
    return 'this is fn2'
}

function fn3() {
    let arr = ['apple', 'banana', 'orange']
    return arr.length
}

function fn() {
    fn1()
    fn2()
    console.log('All fn are done')
}

fn()

Une série de comportements de poussée et d'éclatement de pile se sont produits ci-dessus :

1. Tout d'abord, la pile (boîte) est vide au début

2. Exécution, fn est poussé sur la pile en premier et placé en bas de la pile (boîte)

3. Dans la fonction fn, la fonction fn1 est exécutée en premier et fn1 est poussé sur la pile au-dessus de fn

4. La fonction fn1 est exécutée, lorsque vous rencontrez le mot-clé return, return this is fn1, fn1 est retiré de la pile, et maintenant seul fn

reste dans la boîte 5. Retournez à l'intérieur. de fn, une fois fn1 exécuté, la fonction fn2 commence à s'exécuter et fn2 est poussé sur la pile. Mais à l'intérieur de fn2, lorsque fn3 est rencontré, fn3 commence à être exécuté, donc fn3 est poussé sur la pile

. 6. À ce stade, l'ordre de bas en haut dans la pile est : fn3

7. Par analogie, lorsqu'une phrase avec le mot-clé return. est rencontré dans la fonction fn3, fn3 sort de la pile après l'exécution et revient à la fonction fn2 rencontre également le mot-clé return et continue de sortir de la pile.

8. Maintenant, il n'y a que fn dans la pile. Revenez à la fonction fn et exécutez l'instruction console.log('All fn are done'), fn sort de la pile.

9. Maintenant, la pile est à nouveau vide.

Les étapes ci-dessus sont faciles à confondre. Voici l'organigramme :

Regardez l'exécution dans l'environnement du navigateur Chrome :

3. Recursion

Regardons d'abord le JavaScript simple. récursion

function sumRange(num) {
  if (num === 1) return 1;
  return num + sumRange(num - 1)
}

sumRange(3) // 6

La séquence d'exécution de code ci-dessus :

1. La fonction sumRange(3) est exécutée, sumRange(3) est poussée sur la pile et le mot-clé return est rencontré, mais il ne peut pas être retiré de la pile immédiatement. Parce que sumRange(num - 1) est appelé, c'est-à-dire sumRange(2)

2, donc sumRange(2) est poussé sur la pile, et ainsi de suite, sumRange(1) est poussé sur la pile,

3, Enfin, sumRange(1) sort de la pile et renvoie 1, sumRange(2) sort de la pile et renvoie 2, sumRange(3) sort la pile

4, donc le résultat de 3 + 2 + 1 est 6

Regardez l'organigramme

Ainsi, la récursivité est également un processus consistant à pousser et à faire éclater la pile.

La récursivité peut être exprimée comme non récursive. Ce qui suit est l'exécution équivalente de l'exemple récursif ci-dessus

// for 循环
function multiple(num) {
    let total = 1;
    for (let i = num; i > 1; i--) {
        total *= i
    }
    return total
}
multiple(3)

Notes sur la récursivité

Si l'exemple ci-dessus est modifié, ce sera comme suit :

function multiple(num) {
    if (num === 1) console.log(1)
    return num * multiple(num - 1)
}

multiple(3) // Error: Maximum call stack size exceeded

Il n'y a pas de phrase de mot-clé de retour dans la première ligne du code ci-dessus car il n'y a pas de condition de terminaison pour la récursivité. , il sera toujours poussé sur la pile, provoquant une fuite de mémoire.

Points d'erreur sujets à la récursion

1. Aucun point de terminaison n'est défini

2. À l'exception de la récursivité, d'autres Code des pièces

3. Quand la récursivité est-elle appropriée ?

D'accord, ce qui précède est le concept de récursivité en JavaScript.

Les questions suivantes sont des questions pratiques.

6. Questions pratiques

1. Écrivez une fonction qui accepte une chaîne et renvoie une chaîne qui est l'inverse de la chaîne d'origine.

2. Écrivez une fonction qui accepte une chaîne et compare un caractère de l'avant vers l'arrière, si les deux sont égaux, renvoyez vrai. S'ils ne sont pas égaux, renvoyez faux.

3. Écrivez une fonction qui accepte un tableau et renvoie un nouveau tableau aplati.

4. Écrivez une fonction qui accepte un objet si la valeur de l'objet est un nombre pair, additionnez-les et renvoyez la valeur totale.

5. Écrivez une fonction qui accepte un objet et renvoie un tableau. Ce tableau comprend toutes les valeurs de l'objet qui sont des chaînes

Réponse de référence .

Référence 1

function reverse(str) {
   if(str.length <p>Référence 2</p><pre class="brush:php;toolbar:false">function isPalindrome(str){ 
    if(str.length === 1) return true;
    if(str.length === 2) return str[0] === str[1]; 
    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1)) 
    return false; 
}
var str = 'abba'
isPalindrome(str)

Référence 3

function flatten (oldArr) {
   var newArr = [] 
   for(var i = 0; i <p>Référence 4</p><pre class="brush:php;toolbar:false">function nestedEvenSum(obj, sum=0) {
    for (var key in obj) { 
        if (typeof obj[key] === 'object'){ 
            sum += nestedEvenSum(obj[key]); 
        } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0){ 
            sum += obj[key]; 
        }
     } 
     return sum;
}
nestedEvenSum({c: 4,d: {a: 2, b:3}})

Référence 5

function collectStrings(obj) {
    let newArr = []
    for (let key in obj) {
        if (typeof obj[key] === 'string') {
            newArr.push(obj[key])
        } else if(typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
           newArr = newArr.concat(collectStrings(obj[key]))
        }
    }
    return newArr
}
var obj = {
        a: '1',
        b: {
            c: 2,
            d: 'dd'
        }
    }
collectStrings(obj)

5.Résumé

L'essence de la récursion est que vous devez souvent penser d'abord à la partie régulière Lorsque vous envisagez la partie récursive, voici les méthodes couramment utilisées dans la récursion JavaScript

Array : slice, concat

String : slice, substr, substring

Object : Object.assign

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!