Узнайте о рекурсии в JavaScript

внешний интерфейс JavaScript

Введение

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

В этой статье я приведу вам два примера, чтобы дать вам представление о том, как работают рекурсивные функции.

Контур
  • что такое рекурсия
  • рекурсия чисел
  • рекурсия массива
  • Суммировать

что такое рекурсия

Рекурсия функции заключается в вызове самой себя в функции, посмотрите на простой пример:

function doA(n) {
    ...
    doA(n-1);
}

Чтобы понять, как работает рекурсия в теории, давайте начнем с примера, не зависящего от кода. Представьте, что вы оператор компании. Поскольку это загруженная компания, ваш стационарный телефон подключен к нескольким линиям, поэтому вы можете одновременно принимать несколько вызовов. Каждая строка соответствует кнопке на приемнике, которая будет мигать при поступлении входящего вызова. Когда вы пришли сегодня в офис, чтобы начать работу, там было четыре очереди с мигающими кнопками, поэтому вам нужно было ответить на все эти звонки.

You connect line one and tell him "please wait", then you connect line two and tell him "please wait", then you connect line three and also tell him "please wait", and finally, You connect to Line Four and talk to Это.当你结束了与线路四的通话之后，你回过头来接通线路三，当你结束了与线路三的通话之后，你接通线路二，结束之后，你再接通线路一，当与线路一的这位客户结束通话后，你终于可以放下电话了。

Каждый вызов в этом примере подобен рекурсивному вызову некоторой функции. Когда вы получаете вызов и не можете обработать его немедленно, вызов будет приостановлен; когда у вас есть вызов функции, который не нужно запускать немедленно, он зависнет в стеке вызовов. Когда вы можете ответить на вызов, линия подключена; когда ваш код может инициировать вызов функции, он удаляется из стека вызовов. Вспомните эту аналогию, когда вас немного смутят следующие примеры кода.

рекурсия чисел

Каждой рекурсивной функции необходимо условие завершения, чтобы она не зацикливалась бесконечно. Однако простого добавления условия завершения недостаточно, чтобы избежать бесконечного цикла. Функция должна шаг за шагом приближаться к условию завершения. В рекурсивных шагах проблема постепенно сводится к более мелким проблемам.

Предположим, есть функция: сложить от 1 до n. Например, когда n = 4, реализуется «1 + 2 + 3 + 4».

Во-первых, нам нужно найти условие завершения. Этот шаг можно рассматривать как поиск условия, которое напрямую завершает проблему без рекурсии. Когда n равно 0, дальнейшее разбиение не происходит, поэтому наша рекурсия останавливается, когда достигает 0.

На каждом шаге вы будете вычитать 1 из текущего числа. Что такое рекурсивное условие? заключается в вызове функции с уменьшенным числомsum.

function sum(num){
    if (num === 0) {
        return 0;
    } else {
        return num + sum(--num)
    }
}
 
sum(4);     //10

Каждый шаг выглядит следующим образом:

  • Выполнить сумму (4).
  • 4 равно 0? Нет, оставьте sum(4) и выполните sum(3).
  • 3 равно 0? Нет, оставьте sum(3) и выполните sum(2).
  • 2 равно 0? Нет, оставьте sum(2) и выполните sum(1).
  • 1 равно 0? Нет, оставьте sum(1) и выполните sum(0).
  • 0 равен 0? Да, вычислить сумму (0).
  • Извлечь сумму (1).
  • Извлечь сумму (2).
  • Извлечь сумму (3).
  • Извлечь сумму (4).

Вот еще один способ увидеть, как функция обрабатывает каждый вызов:

sum(4)
4 + sum(3)
4 + ( 3 + sum(2) )
4 + ( 3 + ( 2 + sum(1) ))
4 + ( 3 + ( 2 + ( 1 + sum(0) )))
4 + ( 3 + ( 2 + ( 1 + 0 ) ))
4 + ( 3 + ( 2 + 1 ) )
4 + ( 3 +  3 ) 
4 + 6 
10

Мы можем обнаружить, что параметры в рекурсивном условии продолжают изменяться и постепенно приближаются и, наконец, удовлетворяют условию завершения. В приведенном выше случае мы уменьшаем параметр на 1 на каждом шаге в условии рекурсии и, наконец, проверяем, равен ли параметр 0 в условии завершения.

Задача
  1. Напишите функцию суммирования, которая суммирует числа, используя обычные методы цикла, а не рекурсию.
  2. Напишите рекурсивную функцию для умножения двух чисел. Например:multiply(2,4)вернет 8, выпишуmultiply(2,4)что происходит на каждом этапе.

рекурсия массива

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

Рассмотрим использование массива в качестве аргумента на функцию суммирования и вернуть сумму всех элементов в массиве. Функция суммирования выглядит следующим образом:

function sum(arr) {
    var len = arr.length;
    if (len == 0) {
        return 0;
    } else {
        return arr[0] + sum(arr.slice(1));
    }
}

Если длина массива равна 0, возвращается 0,arr[0]представляет первый бит массива,arr.slice(1)Указывает, что массив arr перехватывается с первого бита и возвращается перехваченный массив. Напримерvar arr = [1,2,3,4];,arr[0]1,arr.slice(1)для[2,3,4]. когда мы выполняемsum([1,2,3,4])Когда, что случилось?

sum([1,2,3,4])
1 + sum([2,3,4])
1 + ( 2 + sum([3,4]) )
1 + ( 2 + ( 3 + sum([4]) ))
1 + ( 2 + ( 3 + ( 4 + sum([]) )))
1 + ( 2 + ( 3 + ( 4 + 0 ) ))
1 + ( 2 + ( 3 + 4 ) )
1 + ( 2 + 7 ) 
1 + 9
10

Каждое выполнение проверяет, пуст ли массив, в противном случае рекурсивно выполняет массив с уменьшающимся количеством элементов.

Задача
  1. Напишите функцию суммирования, которая суммирует массив, используя обычные методы цикла, а не рекурсию.
  2. определитьlength()Функция, которая принимает массив в качестве параметра и возвращает длину массива (вы не можете использовать встроенное свойство длины объекта Javascript Array). Например:length(['a', 'b', 'c', 'd']), и напишите, что произошло на каждом шаге.

Суммировать

Процедура или функция в своем определении или описании имеет метод прямого или косвенного вызова самой себя, который обычно преобразует большую и сложную проблему в меньшую проблему, аналогичную исходной задаче для решения.Только рекурсивная стратегия.Небольшое количество программ может быть используется для описания повторяющихся вычислений, необходимых для процесса решения задачи, что значительно сокращает объем кода программы.

В этой статье перечислены только два небольших случая, просто чтобы проиллюстрировать, что происходит с рекурсией.Формулы двух приведенных выше случаев в виде переменных + функций.Конечно, есть много случаев в виде функций + функций, таких как и упомянутая в начале статьи знаменитая последовательность Фибоначчи, код выглядит следующим образом:

function func( n ) { 
    if (n == 0 || n == 1) {
        return 1;
    }
        return func(n-1) + func(n-2);
}

Давайте поговорим о шагах, преимуществах и недостатках использования рекурсии.

шаг
  1. Найдите правило, преобразуйте это правило в формулу и верните его.
  2. Найдите выход, выход - это условие завершения, это должно быть известное условие.
преимущество
  1. Код на удивление лаконичен.
  2. в соответствии с человеческим мышлением.
недостаток
  1. Поскольку рекурсия заключается в вызове самой функции, а вызов функции требует времени и места: для каждого вызова в стеке памяти выделяется место для хранения параметров, временных переменных, адресов возврата и т. д., а также для проталкивания и извлечения данных в стек нужно тратить время. Это неизбежно приведет к значительному снижению эффективности.
  2. Большинство вычислений в рекурсии повторяются.Суть в том,чтобы разбить задачу на множество маленьких задач.Между маленькими задачами есть перекрывающиеся части.Такие повторные вычисления также приведут к низкой эффективности.
  3. Стек вызовов может переполниться. У стека есть предел емкости.При слишком большом количестве уровней вызовов предел емкости стека будет превышен, что приведет к переполнению стека!

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

Спасибо за прочтение!

Категории