Advertisement
  1. Code
  2. JavaScript

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

by
Read Time:8 minsLanguages:

Russian (Pусский) translation by Ilya Nikov (you can also view the original English article)

Введение

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

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

Содержание:

  • Что такое рекурсия?
  • Рекурсия с цифрами
  • Рекурсия со списками
  • Построение списков
  • Обзор

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

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

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

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

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

Рекурсия с цифрами

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

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

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

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

Это то, что происходит на каждом шагу:

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

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

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

Задача

  1. Реализуйте функцию sum, используя цикл вместо рекурсии.
  2. Создайте функцию, которая рекурсивно перемножает два числа. Например, multiply(2,4) вернет 8. Напишите, что происходит на каждом шаге для multiply(2,4).

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

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

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

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

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

Задача

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

Построение списков

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

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

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

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

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

Задача

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

Обзор

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

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

Отличным ресурсом для продолжения изучения рекурсии является книга The Little Schemer. Она учит вас мыслить рекурсивно, используя формат вопросов и ответов.

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.