Статьи

Понимание рекурсии с помощью JavaScript

Декабрь 20, 2018

Вступление

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

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

Содержание:

  • Что такое рекурсия?
  • Рекурсия с номерами
  • Рекурсия со списками
  • Строительные списки
  • Рассмотрение

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

Рекурсивно определенная функция — это функция, которая определяется в терминах ее более простой версии. Это упрощенный пример:

1
2
3
4
function doA(n) {
    …
    doA(n-1);
}

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

Вы берете первую строку и говорите им: «Пожалуйста, подождите». Затем вы берете вторую строку и переводите их в режим ожидания. Затем вы берете третью строку и переводите их в режим ожидания. Наконец, в четвертой строке вы отвечаете и говорите с абонентом. Когда вы закончите с четвертым абонентом, вы вешаете трубку и отвечаете на третий звонок. Когда вы заканчиваете третий звонок, вы кладете трубку и отвечаете на второй звонок. Когда вы заканчиваете со вторым звонком, вы кладете трубку и принимаете первый звонок. Когда вы закончите этот звонок, вы можете наконец положить трубку.

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

Рекурсия с номерами

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

Предположим, у вас есть функция, которая будет суммировать числа от 1 до n. Например, если n = 4, это будет сумма 1 + 2 + 3 + 4.

Сначала мы определим базовый вариант. Поиск базового случая также можно рассматривать как поиск случая, когда проблема может быть решена без рекурсии. В этом случае это когда n равно нулю. Ноль не имеет частей, поэтому наша рекурсия может остановиться, когда мы достигнем 0.

На каждом шаге вы будете вычитать один из текущего числа. Что такое рекурсивный случай? Рекурсивный случай — это сумма функций, вызываемая с уменьшенным числом.

1
2
3
4
5
6
7
8
9
function sum(num){
    if (num === 0) {
        return 0;
    } else {
        return num + sum(—num)
    }
}
 
sum(4);

Это то, что происходит на каждом этапе:

  • Перейти к сумме (4).
  • 4 равно 0? Нет. Переведите сумму (4) в режим ожидания и перейдите к сумме (3).
  • 3 равно 0? Нет. Переведите сумму (3) в режим ожидания и перейдите к сумме (2).
  • 2 равно 0? Нет. Переведите сумму (2) в режим ожидания и перейдите к сумме (1).
  • 1 равно 0? Нет. Переведите сумму (1) в режим ожидания и перейдите к сумме (0).
  • 0 равно 0? Да. Оцените сумму (0).
  • Возьмите сумму (1).
  • Возьмите сумму (2).
  • Возьмите сумму (3).
  • Возьмите сумму (4).

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

01
02
03
04
05
06
07
08
09
10
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. Реализуйте функцию суммирования, используя цикл вместо рекурсии.
  2. Создайте функцию, которая рекурсивно умножает два числа. Например, multiply(2,4) вернет 8. Напишите, что происходит на каждом шаге для multiply(2,4) .

Рекурсия со списками

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

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

1
2
3
4
5
6
7
function sum(l){
    if (empty(l)) {
        return 0;
    } else {
        return car(l) + sum(cdr(l));
    }
}

empty функция возвращает true, если в списке нет элементов. Функция car возвращает первый элемент в списке. Например, car([1,2,3,4]) возвращает 1. Функция cdr возвращает список без первого элемента. Например, cdr([1,2,3,4]) возвращает [2,3,4]. Что происходит, когда мы выполняем sum([1,2,3,4]) ?

01
02
03
04
05
06
07
08
09
10
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. Например, length(['a', 'b', 'c', 'd']) должна возвращать 4. Напишите, что происходит на каждом шаге.

Строительные списки

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

01
02
03
04
05
06
07
08
09
10
11
function remove(item, l){
    if (empty(l)) {
        return [];
    } else if (eq(car(l), item)) {
        return cdr(l);
    } else {
        return cons(car(l), remove(item, cdr(l)));
    }
}
 
remove(‘c’, [‘a’, ‘b’, ‘c’, ‘d’]) //[‘a’, ‘b’, ‘d’]

Здесь функция eq возвращает true, если оба входа одинаковы. Функция cons принимает элемент и список в качестве входных данных и возвращает новый список с элементом, добавленным в его начало.

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

Мы будем продолжать удалять элементы, пока не достигнем нашего базового варианта, который является пустым списком. Пустой список означает, что мы прошли все пункты в нашем списке. Что делает remove('c', ['a', 'b', 'c', 'd']) ?

1
2
3
4
5
6
remove(‘c’, [‘a’, ‘b’, ‘c’, ‘d’])
cons( ‘a’, remove(‘c’, [‘b’, ‘c’, ‘d’]) )
cons( ‘a’ , cons( ‘b’, remove(‘c’, [‘c’, ‘d’]) ))
cons( ‘a’, cons( ‘b’, [‘d’] )
cons( ‘a’, [‘b’, ‘d’])
[‘a’, ‘b’, ‘d’]

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

задача

  1. Перепишите функцию удаления, чтобы она использовала циклы вместо рекурсии для удаления элемента из списка.
  2. Измените функцию удаления, чтобы она удаляла все вхождения элемента из списка. Например, remove('c', ['a', 'b', 'c', 'd', 'c'] возвращает [‘a’, ‘b’, ‘d’]. Напишите, что происходит, шаг за шагом шаг.

Рассмотрение

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

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

Большим ресурсом для продолжения изучения рекурсии является книга «Маленький интриган» . Он учит вас, как рекурсивно мыслить, используя формат вопросов и ответов.

38
Share: