• Функция, вызывающая себя из собственного блока кода. Любая функция, которая вызывает сама себя, является рекурсивной функцией.
  • Способ решения проблемы путем разбиения ее на более мелкие версии самой себя

Рекурсивный паттерн:

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

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

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

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

  • Базовый случай: Простейший возможный случай этой проблемы - если вы сидите в самом первом ряду и не видите никаких рядов перед собой. Это будет наш базовый вариант. Если прямо перед вами нет ряда, значит, вы должны быть в первом ряду.
  • Логика приближения к базовому случаю: Если вам не повезло оказаться в первом ряду, вам нужно каким-то образом придумать, как разбить проблему и перейти к базовому варианту. Вы знаете, что вы не в первом ряду. Вы знаете, что из всех людей в театре только люди в первом ряду знают свой номер. Возможное решение - спросить человека перед вами, находится ли он в первом ряду. Если они скажут «нет», попросите этого человека задать человеку перед ним тот же самый вопрос. Продолжайте, повторяя эту схему, пока кто-нибудь не подтвердит, что они сидят в первом ряду. Как только этот человек подтвердит, что он находится в строке 1, он может сказать человеку, стоящему за ним, который теперь знает, что он должен быть в строке 2. Теперь информацию можно передавать обратно, строка за строкой, пока она не достигнет вас, и вы сможете сделать вывод, что вы на 1 строку выше любого номера строки, который сказал человек перед вами.

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

  • Базовый вариант: если получить куклу без кукол внутри, мы можем с уверенностью сказать, что внутри нет кукол.
  • Логика приблизиться к базовому варианту: проверьте, есть ли внутри кукла. Если да, то проверьте, есть ли внутри кукла, и так до тех пор, пока внутри не останется кукол. Как только мы находим куклу без кукол внутри, мы знаем, что кукла, в которой она была, поэтому имела 1 куклу внутри, а в предыдущей - 2 куклы.

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

Более практичный пример:

Напишите функцию (сумму), которая при задании числа (n) возвращает сумму всех чисел от n до 1. Входное число всегда будет 1 или больше.

  • бывший. Если дано 5, вернуть сумму 5 + 4 + 3 + 2 + 1 → 15.
  • Базовый случай: если (n === 1) вернуть 1
  • Пошаговая логика: сумма (n) = sum (n-1) + n

Давайте разберемся с этой логикой простым английским языком. Представьте, что вы компьютер. Программист дает вам только базовый случай и пошаговую логику: если n === 1, то верните 1, иначе верните сумму (n-1) + n.

Рассмотрим пример, в котором нам (как компьютеру) дается задание вычислить сумму (5), то есть 5 + 4 + 3 + 2 + 1. Мы не знаем, что такое сумма (5), но мы знаем, что она равна сумме (4) + 5, поскольку есть логика, написанная, что сумма (n) = sum (n-1) + n. Мы не знаем, что такое сумма (4), но мы знаем, что она равна сумме (3) + 4. Мы не знаем, что такое сумма (3), но мы знаем, что она равна сумме (2) +3. Мы не знаем, что такое сумма (2), но знаем, что она равна сумме (1) + 2.

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

Сумма (2), которая, как мы сказали, равна сумме (1) + 2, теперь может быть решена. sum (1) вернула 1, поэтому sum (2) = 1+ 2, что равно 3. Теперь можно решить сумму (3), которая, как мы сказали, равна сумме (2) + 3. Sum (2) вернула 3, поэтому sum ( 3) = 3+ 3, что равно 6. Мы продолжаем двигаться вверх по стеку, пока не решим наш первоначальный вопрос и не вернем 15.

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

Стек вызовов

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

Пример: вы хотите пообедать и написать список задач для этого:

  • Покинуть дом
  • Поездка в магазин
  • Выбрать все ингредиенты
  • Оплатить еду
  • Ехать домой
  • Войти в дом
  • Ингредиенты для стирки
  • готовить еду
  • Ужинать

Каждая задача не может быть завершена до тех пор, пока не будет завершена та, которая была до ее завершения. Если вы хотите поужинать, вам нужно сначала приготовить еду. Если вы хотите приготовить еду, вам, вероятно, следует перед этим вымыть мясо и овощи и так далее. Это не слишком отличается от примеров из театра, матрешки и рекурсивной суммы. Наш конечный результат зависит от результата каждого шага перед ним. Каждый сделанный нами шаг добавляется в этот стек вызовов и удаляется только тогда, когда он возвращает значение. Мы можем готовить пищу только тогда, когда у нас есть ингредиенты для приготовления. Мы можем определить номер нашей строки только тогда, когда строка перед нами знает номер своей строки. Мы можем определить количество кукол только тогда, когда мы знаем количество кукол в следующей самой маленькой кукле. Мы можем вычислить сумму от 1 до 100, только если мы знаем сумму от 1 до 99. Начинаете видеть закономерность?

Последовательность и рекурсия Фибоначчи

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

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

Пример: 0,1,1,2,3,5,8,13…

  • Обратите внимание, что мы начинаем с 0 и 1, но начальные числа могут различаться в разных представлениях последовательности.
  • 0-й номер последовательности равен 0
  • 1-й номер последовательности равен 1
  • 2-е число последовательности - это сумма 0-го и 1-го чисел (0 + 1 = 1)
  • 3-е число последовательности - это сумма 1-го и 2-го чисел (1 + 1 = 2)
  • Этот образец продолжается бесконечно.

Проблема: напишите функцию с именем fib, которая возвращает n-е число (n) последовательности Фибоначчи. Последовательность всегда начинается с 0 как 0-го числа и 1 как 1-го числа в последовательности.

  • Бывший. Если дано 4, нам нужно вернуть 3, так как 4-е число последовательности равно 3 (0,1,1,2, 3).
  • Обратите внимание, что мы называем первое число в последовательности нулевым числом. Во многих языках программирования списки или последовательности имеют нулевой индекс, то есть первый элемент называется 0-м. Это пригодится для решения нашей текущей проблемы, как вы увидите ниже.

Базовый вариант:

  • Если (n === 0) вернуть 0
  • если (n === 1) вернуть 1
  • Это можно переписать в одной строке как: if (n ‹2) return n.

Здесь нам помогает нулевая индексация. Если мы назовем первое число в последовательности 1-м, а второе число - 2-м, мы не сможем записать базовый случай как одну строку.

Примечание: поскольку нам нужно как минимум 2 числа, чтобы установить шаблон, т.е. чтобы найти следующий номер последовательности, у нас действительно есть 2 базовых случая (0 и 1).

Пошаговая логика:

  • Если n не равно 0 или 1…
  • вернуть fib (n-2) + fib (n-1)

Давайте рассмотрим эту логику более внимательно. Еще раз представьте, что вы - компьютер, который знает возвращаемое значение только в том случае, если на входе 0 или 1. Как бы вы определить возвращаемое значение, скажем, 7? или 50? или 1000? Чтобы не усложнять задачу, давайте возьмем 7 в качестве нашего примера. Мы можем сказать, что не знаем, что такое 7-е число в последовательности, но мы знаем, что это результат сложения 5-го и 6-го чисел. Точно так же мы не знаем, что такое 5-е и 6-е числа, но мы знаем, что они являются результатом сложения 3-го и 4-го, 4-го и 5-го чисел соответственно. Шаблон продолжается до тех пор, пока не будет достигнут базовый вариант (0 или 1), в котором предоставляется возвращаемое значение и передается обратно в стек, шаг за шагом к нашей начальной точке.

Давайте рассмотрим схему:

Пусть вас не пугает эта, казалось бы, сложная диаграмма. Мы следуем той же схеме, что и все наши предыдущие примеры. Вы можете видеть, что, начиная с верхнего fib (7) (обозначающего n), мы разветвляемся влево с помощью fib (5) (представляющего n-2) и ветвимся вправо с помощью fib (6) (представляющего n-1). Оттуда мы продолжаем разветвляться, причем каждый вызов fib (n) равен fib (n-2) + fib (n-1), пока мы не достигнем одного из наших базовых случаев (fib (0) или fib (1) ).

Когда мы попадаем в базовый вариант, они выводят 0 или 1 соответственно.

Теперь fib (2) может быть решена.

  • фиб (2) = фиб (0) + фиб (1)
  • фиб (2) = 0 + 1
  • фиб (2) = 1

Теперь fib (3) может быть решена

  • фиб (3) = фиб (1) + фиб (2)
  • фиб (3) = 1 + 1
  • фиб (3) = 2

Теперь fib (4) может быть решена

  • фиб (4) = фиб (2) + фиб (3)
  • фиб (4) = 1+ 2
  • фиб (4) = 3

Теперь fib (5) может быть решена

  • фиб (5) = фиб (3) + фиб (4)
  • фиб (5) = 2+ 3
  • фиб (5) = 5

Теперь fib (6) может быть решена

  • фиб (6) = фиб (4) + фиб (5)
  • фиб (6) = 3+ 5
  • фиб (6) = 8

Наконец, fib (7) может быть решена

  • фиб (7) = фиб (5) + фиб (6)
  • фиб (7) = 5+ 8
  • fib (7) = 13

Мы решили проблему!

Зачем нужна рекурсия?

Прелесть рекурсии в том, что независимо от размера входных данных или сложности задачи - шаблон остается неизменным. Хотим ли мы узнать сумму от 1 до 5 или от 1 до триллиона, мы следуем одним и тем же правилам. Установите базовый вариант, при котором рекурсия остановится. Работайте над этим базовым вариантом, шаг за шагом. Как только базовый вариант будет достигнут, возьмите возвращаемое значение и передайте его обратно в стек, шаг за шагом, пока не решите исходный вопрос.

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

В заключении…

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

Независимо от того, насколько далеко вы чувствуете себя от мастерства, сделайте один шаг, и вы станете на шаг ближе. Удачного обучения!