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

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

Пример, который я буду использовать, чтобы продемонстрировать, это факториал. Другое имя, довольно устрашающее, но простое. Факториал - это произведение числа n и всех чисел, находящихся под ним. Написано со знаком «!» после числа. Итак 4! (факториал 4) равен 24. Когда мы его записываем, это всего лишь 4 x 3 x 2 x 1.

Вот код:

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

Это сложно объяснить простым текстом, поэтому именно здесь наша визуализация приходит в затруднительное положение. Будем решать факториал (6) или 6 !.

Как только мы вызываем нашу функцию factorial (6), она помещается в стек вызовов.

Мы проверяем, выполняется ли наш базовый случай, однако 6 не равно 1. Итак, затем нам нужно вернуть произведение 6 и факториала (5). Однако, поскольку нам нужно разрешить factorial (5), вызов функции для factorial (6) теперь просто ожидает в стеке вызовов.

Как только мы вызываем factorial (5), мы добавляем его в начало стека вызовов.

Опять же, мы проверим, выполняется ли наш базовый вариант. 5 не равно 1, поэтому он не соблюден. Нам нужно вернуть произведение 5 и факториала (4). Нам нужно, чтобы факториал (4) был разрешен, прежде чем мы сможем что-либо вернуть, поэтому теперь он ожидает наверху нашего стека вызовов.

Теперь factorial (4) будет помещен в верхнюю часть стека вызовов.

Наше число 4 не равно 1, поэтому наш базовый вариант еще не выполнен. Мы рекурсивно вызовем функцию факториала снова и вернем произведение этого вызова и 4.

После вызова factorial (3) он помещается в верхнюю часть стека.

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

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

Наконец, когда мы, наконец, встретили наш базовый случай с factorial (1), мы можем увидеть, как теперь выглядит наш завершенный стек вызовов.

Каждый элемент в нашем стеке вызовов ожидает разрешения элемента над ним, чтобы разрешиться сам. По сути, мы сейчас идем в обратном порядке. Мы начнем процесс извлечения элементов из нашего стека вызовов. Теперь, когда мы можем окончательно вернуть значение для factorial (1), в данном случае это значение равно 1, мы можем извлечь его из стека.

Factorial (1) вернул 1. Это возвращаемое значение теперь можно использовать для разрешения следующего элемента в стеке вызовов, factorial (2). И помните, что в нашем коде мы возвращаем num * factorial (num -1), что равно 2 * 1. Теперь мы можем извлечь это из стека вызовов.

Теперь мы можем использовать это возвращаемое значение для решения следующего элемента в нашем стеке вызовов, который является факториалом (3). Num равно 3, а factorial (2) вернул нам 2. Итак, из factorial (3) мы возвращаем 3 * 2, что равно 6. Теперь мы можем извлечь это из стека вызовов.

Этот шаблон будет продолжаться, когда мы вернемся в конец стека. Теперь нам нужно возвращаемое значение от factorial (4), равное 24. Это произведение num, 4 и factorial (3), которое вернуло 6. Factorial (4) теперь может быть извлечен из стека вызовов.

Мы почти вернулись в конец стопки. Но к настоящему моменту вы должны научиться этому. Теперь мы возвращаем значение из factorial (5). Мы умножаем num, 5 и возвращаемое значение factorial (4), равное 24, и получаем 120. Теперь Factorial (5) может быть извлечен из нашего стека.

Теперь мы добрались до конца нашего стека вызовов после разрешения всех остальных вызовов функций, которые находились над ним в стеке. Наконец, мы можем вернуть наш исходный вызов функции, который является факториалом (6). Это вернет произведение num, 6, и значение, возвращенное из factorial (5), 120. Этот последний вызов функции может быть удален из стека вызовов.

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

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

Если у вас есть вопросы или комментарии, дайте мне знать! Вы можете найти меня в Твиттере по адресу @ a_cisneros45.