Чтобы понять рекурсию, нужно понять рекурсию
Рекурсия - это способ решения задачи, при котором вы решаете отдельные небольшие части задачи, пока не решите её всю целиком. Метод или функция называются рекурсивными, если они могут вызывать сами себя:
Обратите внимание на базовый случай и рекурсивный вызов приведенном выше примере, которые и делают данный алгоритм рекурсивным.
В рекурсивных функциях обязательно должен быть базовый случай, внутри которого не совершается рекурсивный вызов.
Лучший способ объяснить рекурсию — рассмотреть примеры, так что давайте рассмотрим две наиболее часто встречающиеся задачи, решаемые с применением рекурсии.
Пример 1: вычисление факториала числа
Вычисление факториала числа — распространенная задача, которую можно решить рекурсивно. Напомним, что факториал числа n обозначается как n! и является произведением всех чисел от 0 до n. Например, 5! равно 5*4*3*2*1, что в результате даёт 120.
Рассмотрим сначала итеративное решение:
Это хорошее решение, но давайте попробуем сделать то же самое при помощи рекурсии. Когда мы ищем рекурсивное решение задачи, нам нужно понять, какими будут наши подзадачи. Давайте попробуем разбить нашу задачу на составляющие подзадачи:
- Мы знаем, что factorial(5) = 5 * factorial(4), или 5! = 5 * 4!.
- Продолжая, можно сказать, что factorial(5) = 5 * (4 * factorial(3)), или 5 * (4 * (3 * factorial(2)). И так далее…
- …Пока не получим 5 * 4 * 3 * 2 * 1. На этом этапе у нас останется только одна подзадача — найти 1!.
- factorial(1) и factorial(0) всегда равны 1, так что это и будет наш базовый случай.
Используя такой подход, мы можем написать рекурсивное решение нашей задачи:
Пример 2: ряд Фибоначчи
Еще одна задача, которую можно решить рекурсивно, это задача с числами Фибоначчи. Напомним, что последовательность Фибоначчи это ряд чисел 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 и так далее.
Все эти числа укладываются в определенный шаблон: каждое число равно сумме двух предыдущих. То есть, 0 + 1 = 1; 1 + 1 = 2; 1 + 2 = 3; 2 + 3 = 5 и т. д.
Таким образом, число Фибоначчи на позиции n (когда n > 2) это сумма числа Фибоначчи на позиции (n - 1) и числа Фибоначчи на позиции (n - 2).
Опять же, будет полезным привести сначала итеративное решение:
Как видите, рекурсивное решение выглядит намного проще:
При вызове функции fibonacci(5) будут сделаны следующие вызовы:
Ряд Фибоначчи с мемоизацией
Стоит упомянуть еще один подход к решению этой задачи — так называемую мемоизацию. Мемоизация («запоминание») представляет собой технику оптимизации, при которой сохраняются результаты предыдущих вычислений (это похоже на кеширование). Благодаря этой технике мы можем ускорить работу нашего рекурсивного решения.
Если вы посмотрите на приведенную выше схему вызовов рекурсивной функции для вычисления fibonacci(5), вы увидите, что fibonacci(3) вычислялось дважды. Поэтому мы можем сохранить результат первого вычисления, чтобы при втором случае воспользоваться уже готовым ответом.
Посмотрите, как изменяется наше решение при добавлении мемоизации:
Зачем использовать рекурсию?
Честно говоря, рекурсивное решение практически всегда медленнее итеративного. Но при этом рекурсивные решения куда проще читать (вспомните пример с решениями по числам Фибоначчи), а мемоизация позволяет сократить отставание в скорости. В целом рекурсия проще для понимания, к тому же такие решения требуют меньше кода.
Заключение
Теперь, когда мы разобрали пару примеров, надеемся, что вам стало легче разобраться в теме рекурсии и понять, зачем вообще ее использовать.
Рекомендуем потренироваться в решении задач на рекурсию на HackerRank.