Рекурсия — это просто решение проблемы.

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

К этому видео было подготовлено видео: https://youtu.be/WhdJbN584-o — так почему бы не посмотреть его?

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

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

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

Мы можем повеселиться с этим:

Как бы вы сказали компьютеру, чтобы узнать, является ли кто-то потомком Чингисхана? Возможно, алгоритм определения того, кто является потомком Чингисхана, а кто нет, будет выглядеть так:

The person is an heir to Ghengis Khan if his/her father is named Ghengis Khan, or his/her father or mother is an heir to Ghengis Khan.

Небольшое упражнение: как определить, являетесь ли вы наследником? Что вам нужно будет сделать, и что будет включать в себя этот процесс?

Игрушечная проблема

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

Итеративно мы можем записать решение:

с этой простой таблицей трассировки, объясняющей логику countDown(2)

У нас также есть рекурсивная версия для сравнения. Обратите внимание, как функция вызывает сама себя.

Если пользователь запустил рекурсивный код с помощью countDown(2), мы продолжаем выполнение обратного отсчета, пока не достигнем базового случая числа ‹ 1. Этот базовый случай означает, что мы знаем, когда прекратить.

Базовым случаем здесь является следующая строка:

if (num < 1) {return}

Давая нам следующие шаги выполнения:

Здесь мы можем видеть, что происходит. Мы печатаем число для текущего выполнения только в том случае, если параметр больше 1. Когда он меньше, выполнение останавливается. Диаграмма слева представляет стек вызовов. Когда программа вызывает рекурсивную функцию, она перемещается на вершину стека вызовов (это означает, что она будет работать по принципу «последним пришел — первым вышел»).

Это станет ясно из последующих примеров.

Факторы

Факториалы — это произведение целого числа и всех целых чисел под ним; например, факториал четырех ( 4! ) равен 24 (поскольку 24 = 4 * 3 * 2 * 1 ).

Мы можем представить себе, что факториал 4 можно получить, вычислив факториал 3, а затем умножить на 4. 3! = 3 * 2! и 2! = 2 * 1! и наконец 1! =1

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1

Это можно запрограммировать с помощью итеративного метода. Он работает, перебирая все целые числа до (и включая) num и умножая результат на него.

Сухой ход выглядит следующим образом

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

Последовательность Фибоначчи

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

Последовательность состоит из чисел, которые суммируют два числа, непосредственно предшествующие этому числу. Чтобы начать ряд, последовательность Фибоначчи начинается с чисел 0, 1.

Третье число: 0 + 1 = 1

Четвертое число: 1 + 1 = 2

Пятое число: 2 + 1 = 3

Шестое число: 2 + 3 = 5

и так последовательность продолжается.

Итеративная версия алгоритма Фибоначчи выглядит следующим образом (обратите внимание, что я добавил здесь оператор быстрой защиты вместо проверки, которую я использовал выше):

Это очень похоже на приведенную выше факторную последовательность, и выполнение также похоже:

Это обычно представляется как дерево рекурсии

Где мы можем видеть, что fib (4) состоит (непосредственно) из fib (3) и fib (2).

Это нормально, но мы видим много повторяющихся вызовов функций fib(2) и fib(1).

Есть техника минимизации этих вызовов — динамическое программирование.

Это то, что я расскажу в более позднем посте.