Блог

О рекурсии просто и пошагово

Редакция Lodoss Team
0

Как говорил Стивен Хокинг: «Чтобы понять рекурсию, надо сначала понять рекурсию». Знаете ли вы, какие события происходят при вызове функции? Нет? Тогда с этого мы и начнем.

Вызов функции

Когда мы вызываем функцию, контекст выполнения помещается в стек.
Стек — это структура данных, которая работает на основе «первый пришел — последний ушел».

Теперь вернемся к контексту выполнения. Он формируется при вызове функции и ставит себя в стек выполнения. Контекст выполнения имеет свойства, объект активации и привязку this. Привязка this является ссылкой на этот контекст выполнения. Объект активации включает в себя: переданные параметры, объявленные переменные и объявления функций.

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

Рекурсия

Итак, что такое рекурсия?

Рекурсивная функция — это функция, которая вызывает себя до тех пор, пока не будет выполнено «базовое условие» и выполнение не остановится.

В противном случае, мы будем продолжать размещать контексты выполнения поверх стека. Это может происходить до тех пор, пока у нас нет «переполнения стека». Переполнение стека — это когда у нас заканчивается память для хранения элементов в стеке.

В общем случае рекурсивная функция имеет по крайней мере две части: базовое условие и по крайней мере один рекурсивный случай.

Давайте рассмотрим классический пример.

Факториал

Здесь мы пытаемся найти 5! (факториал пяти). Факториальная функция определяется как произведение всех положительных целых чисел, меньших или равных ее аргументу.

Первое условие гласит: «если переданный параметр равен 0 или 1, мы выйдем из функции и вернем 1».

Далее, рекурсивный случай заявляет:

«Если параметр не равен 0 или 1, то мы передадим значение количества вызовов этой функции, равное num, с num-1 в качестве аргумента».

Поэтому, если мы вызываем factorial(0), функция возвращает 1 и никогда не попадает в рекурсивный случай.

То же самое относится и к factorial(1).

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

1.Стек выполнения помещает factorial () с 5 в качестве переданного аргумента. Базовое условие не выполняется, поэтому заходим в рекурсию.
2. Стек помещает factorial () во второй раз с num-1 = 4 в качестве аргумента. Базовое условие не выполняется, поэтому заходим в рекурсию.
3. Стек выполнения помещает factorial () в третий раз с num-1 = (4-1) = 3 в качестве аргумента. Базовое условие не выполняется, поэтому заходим в рекурсию.
4. Стек выполнения помещает factorial () в четвертый раз с num-1 = (3-1) = 2 в качестве аргумента. Базовое условие не выполняется, поэтому заходим в рекурсию.
5. Стек выполнения помещает factorial () в пятый раз с num-1 = (2-1) = 1 в качестве аргумента. Теперь базовое условие выполняется, поэтому возвращается 1.

На этом этапе мы уменьшали аргумент на один при каждом вызове функции, пока не достигли условия возврата 1.

6. Отсюда завершается последний контекст выполнения, num === 1, так что функция возвращает 1.
7. Следующий num === 2, поэтому возвращаемое значение равно 2 (=1х2).
8. Потом num === 3, поэтому возвращаемое значение равно 6 (=2х3).

Пока у нас есть 1х2х3.

9. Далее, num === 4. Возвращаемое значение в новом контексте = 24 (=4х6).
10. Наконец, num === 5. 5х24=120, получаем 120 в качестве конечного значения.

Мы могли бы сделать то же самое с for или while. Но использование рекурсии дает нам аккуратное, элегантное и более читаемое решение.

Вот почему мы используем рекурсивные функции.

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

  1. Подзадачи легче решить, чем исходную задачу.
  2. Решения подзадач комбинируются для решения исходной задачи.

Принцип «разделяй и властвуй» чаще всего используется для обхода или поиска структур данных, таких как бинарные деревья поиска, графики и коллекции данных. Он также работает для многих алгоритмов сортировки, таких как quicksort и heapsort.

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

Фибоначчи

Рекурсивные массивы

Изменение строки

Quicksort

Практика рекурсивных методов важна. Для вложенных структур данных, таких как деревья, графики и массивы, рекурсия неоценима.

Recursion is not hard: a step-by-step walkthrough of this useful programming technique

0