Понимание рекурсии с точки зрения JavaScript

внешний интерфейс алгоритм JavaScript Chrome

исходный адрес

1. Что такое рекурсия?

Концепция рекурсии очень проста, "позвони себе" (функции используются в качестве примера ниже).

Прежде чем анализировать рекурсию, вам нужно понять «стек» в JavaScript (call stack) концепция.

2. Толкай и хлопай

кучачто это такое? Можно понять, что в памяти есть некая область, эта область уподобляется ящику, вы что-то кладете в ящик, это действиетолкать стек. Таким образом, первое, что нужно положить, находится на дне коробки, а последнее, что нужно положить, — наверху коробки. Извлечение вещей из коробки можно понимать какпоп.

Отсюда делается вывод, что у нас есть привычка брать вещи сверху вниз, а вещи, которые кладут первыми, оказываются на дне коробки, и тогда мы можем их доставать последними.

В JavaScript при вызове функции происходит стекирование.returnПосле того, как предложение ключевого слова или выполнение пройдет стек (поп).

Возьмем пример: каков порядок выполнения этого кода?

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()

Выше приведен ряд действий по укладке и извлечению:

  1. Во-первых, стек (коробка) сначала пуст
  2. функцияfnвоплощать в жизнь,fnСначала толкните стопку и положите ее на дно стопки (коробки).
  3. Внутри функции fn сначала выполните функциюfn1,fn1складывать наfnнад
  4. функцияfn1выполнять, сталкиватьсяreturnключевое слово, возвратthis is fn1,fn1Выскочить из стопки, теперь в коробке остался только одинfn
  5. назадfnвнутренний,fn1После выполнения функцияfn2Начать выполнение,fn2толкать стек, но вfn2внутри, встречаfn3,Начать выполнениеfn3,такfn3толкать стек
  6. В это время порядок снизу вверх в стеке следующий:fn3 <= fn2 <= fn,fnвнизу
  7. И так далее, функцияfn3внутренняя встречаreturnпредложения с ключевыми словами,fn3После завершения выполнения извлеките стек и вернитесь к функцииfn2середина ,fn2также столкнулсяreturnключевое слово, продолжайте извлекать стек.
  8. Теперь в стеке только одинfnТеперь вернемся к функцииfnв, выполнитьconsole.log('All fn are done') утверждение,fnвытолкнуть стек.
  9. Теперь стек снова пуст.

Вышеуказанные шаги легко запутать людей, ниже приведена блок-схема:

压栈出栈流程图

Посмотрите на среду браузера CHROME:

chrome 执行顺序

3. Рекурсия

Начнем с простой рекурсии JavaScript

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

sumRange(3) // 6

Последовательность выполнения приведенного выше кода:

  1. функцияsumRange(3)воплощать в жизнь,sumRange(3)стек, встречаreturnключевое слово, но стек не может быть извлечен немедленно, потому что вызовsumRange(num - 1)которыйsumRange(2)
  2. так,sumRange(2)толкать стек и так далее,sumRange(1)толкающий стек,
  3. наконец,sumRange(1)поп возвращает 1,sumRange(2)вытолкнуть стек, вернуть 2,sumRange(3)поп
  4. так3 + 2 + 1результат 6

см. блок-схему

递归执行顺序

Таким образом, рекурсия — это также процесс добавления и извлечения стека.

Рекурсия может быть представлена ​​нерекурсией, ниже приведена эквивалентная реализация приведенного выше рекурсивного примера.

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

4. Рекурсивные точки внимания

Если приведенный выше пример изменить следующим образом:

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

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

Первая строка приведенного выше кода неreturnПредложения с ключевыми словами, поскольку рекурсия не имеет условия завершения, она будет продолжать помещаться в стек, вызывая утечку памяти.

Рекурсия подвержена ошибкам

  1. не задана конечная точка
  2. Помимо рекурсии, другие части кода
  3. Когда уместна рекурсия

Что ж, вышеизложенное — это концепция рекурсии в стиле JavaScript.

Ниже приведены практические вопросы.

6. Практические вопросы

  1. Напишите функцию, которая принимает строку и возвращает строку, которая переворачивает исходную строку.
  2. Напишите функцию, которая принимает строку строк и сравнивает один символ с начала на конец. Если они равны, вернитеtrue, если не равно, вернутьfalse.
  3. Напишите функцию, которая принимает массив и возвращает сглаженный новый массив.
  4. Напишите функцию, которая берет объект, значения которого четны, складывает их вместе и возвращает итог.
  5. Напишите функцию, которая принимает объект и возвращает массив, включающий все значения в объекте в виде строк

7. Справочные ответы

Ссылка 1

function reverse(str) {
   if(str.length <= 1) return str; 
   return reverse(str.slice(1)) + str[0];
}

reverse('abc')

Ссылка 2

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)

Ссылка 3

function flatten (oldArr) {
   var newArr = [] 
   for(var i = 0; i < oldArr.length; i++){ 
    if(Array.isArray(oldArr[i])){ 
        newArr = newArr.concat(flatten(oldArr[i])) 
    } else { 
        newArr.push(oldArr[i])
     }
   }
   return newArr;
}

flatten([1,[2,[3,4]],5])

Ссылка 4

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}})

Ссылка 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. Резюме

Суть рекурсии в том, что часто необходимо сначала подумать о том, как выглядит обычная часть.При рассмотрении рекурсивной части ниже приведены методы, обычно используемые в рекурсии JavaScript.

  • множество:slice, concat
  • нить:slice, substr, substring
  • Объект:Object.assign
Категории