Рекурсия, рекурсия, рекурсия…

Сегодня мы рассмотрим рекурсию. Если вы не были в курсе, это постоянная серия блогов об алгоритмах. Вы отстали всего на 2 поста, так что можете наверстать упущенное в кратчайшие сроки. Часть первая здесь. И часть вторая, по алгоритму Евклида, здесь.

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

Это очень простая рекурсивная функция, которая отсчитывает до 0 от входного числа n, которое мы передаем. Следовательно, если мы запустим countdown(10), мы получим в терминале следующий вывод.

Число выводится на экран с помощью оператора print в строке 6. Это достаточно просто, но как он узнает, что нужно напечатать другие числа? Что ж ... Как уже упоминалось, рекурсивная функция вызывает сама себя, поэтому вы увидите, что в строке 7 мы возвращаем countdown(n — 1). Мы возвращаем ту же функцию, которая выполняется, за исключением того, что на этот раз мы говорим сделать то же самое, но с n — 1. Поэтому, когда мы запускаем countdown(10), он выполняется, выводит 10 на консоль, а затем вызывает countdown(10–1) или countdown(9). При этом выполняется та же процедура: выводит 9 на консоль, а затем вызывает countdown(9–1) или countdown(8). И этот процесс повторяется с 8, затем с 7 и так далее. Вы уловили картину.

Если мы перемотаем вперед, функция прекратит выполнение, когда n == 0. Здесь мы говорим, что если n == 0, то верните n, то есть 0. Это называется базовым случаем. Каждая рекурсивная функция должна иметь базовый случай. Если бы мы этого не сделали, рекурсивная функция никогда бы не остановилась. В нашем примере без базового случая наша функция всегда будет вести обратный отсчет и, вероятно, выйдет из строя наш компьютер, поэтому мы должны указать, когда она должна остановиться. Здесь мы говорим, что он остановится, когда n станет 0. Базовый случай в рекурсии служит той же цели, что и условие в цикле while. Во многих отношениях рекурсия похожа на цикл. Фактически, проблемы, которые решаются с помощью рекурсии, также могут быть решены с помощью итеративного подхода, что означает лишь использование цикла.

Евклид и рекурсия

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

В этом примере функция out gcd_euclid принимает два ввода, и если b истинно (т.е. ненулевое), мы вводим цикл while до b == 0. В этом цикле мы создаем переменную для запоминания значения b, устанавливаем b на остаток от a % b и устанавливаем a на значение b в начале итерации. Мы продолжаем этот процесс до тех пор, пока b не станет 0, что означает, что мы нашли значение, которое делится с остатком 0. В результате он вернет нам наибольший общий делитель двух наших целых чисел. Например, если мы передали это 24 и 36. Он вернет 12. 12 - это наибольшее число, которое входит в оба наших входных параметра: 24 и 36. Достаточно просто.

Однако это решение также может быть решено рекурсивно. Фактически, рекурсивное решение, вероятно, является наиболее распространенным решением. Я переработал наш итеративный пример в рекурсивный.

Здесь решается точно такая же задача - найти наибольший общий делитель между двумя целыми числами. Единственная разница в том, что решение рекурсивно, и мы знаем это, потому что оно вызывает само себя (строка 6). Логика практически такая же, как и у итеративного решения. У нас есть базовый случай: если b falsey (т. Е. Ноль), то вернуть. Это служит точно той же цели, что и условие нашего цикла while в итеративном решении. В итеративном решении, если b имеет значение falsey (т.е. ноль), мы выходим из цикла while и возвращаем a.

Другой аспект этого решения - способ изменения значений a и b. В итеративной функции мы просто перезаписываем значения переменных на новые значения при каждой итерации цикла. В рекурсивном решении мы вместо этого передаем новые значения в качестве параметров функции gcd_recursive и возвращаем ее.

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

Фибоначчи

Фибоначчи - это классическая задача на собеседовании. Вам нужно написать функцию, которая возвращает n-е число Фибоначчи. Принцип работы последовательности Фибоначчи заключается в том, что следующее число в последовательности представляет собой сумму двух предыдущих чисел. Чтобы это сработало, нам нужно начать с двух чисел. Последовательность начинается с 0 и 1. Расширенная последовательность Фибоначчи будет выглядеть так: 0, 1, 1, 2, 3, 5, 8, 13… и так далее. Наша задача - написать функцию fib (n), которая возвращает n-е число Фибоначчи, поэтому fib (0) вернет 0 и fib (5). вернет 5.

Это выглядит довольно аккуратно, но что он делает на самом деле? Базовый случай возвращает значение n. Однако, пока мы не достигнем этого базового случая, мы вернем сумму двух функций. Это сложно осмыслить. Мы можем визуализировать это, чтобы упростить понимание.

Здесь мы изначально вызвали функцию fib(5), поэтому нам нужна пятая последовательность Фибоначчи. Посмотрите на дерево - оно порождается несколькими вызовами функций. fib(5) возвращает fib(5–1) + fib(5–2), что переводится в fib(4) и fib(3). Точно так же они вызывают еще две функции каждая - fib(3) и fib(2) вызываются вызовом fib(4), а fib(2) и fib(1) из нашей функции fib(3). Со мной все еще? Непонятно, правда? Единственный момент в последовательности, где мы возвращаем реальное значение, а не функцию, - это когда n ≤ 1. В этом случае мы возвращаем n. Эти экземпляры обозначены синими квадратами на изображении. Для fib(1) функция возвращает 1. Для fib(0) функция возвращает 0. Если мы сложим все эти числа вместе, мы получим: 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5. Пятый элемент в последовательности Фибоначчи равен 5! Вот как он получает ответ!

Фибоначчи: итерационный подход

Как и было обещано, любой рекурсивный подход также может быть реализован итеративно, поэтому ниже у нас есть итеративное решение проблемы Фибоначчи.

Это довольно простое решение. У нас есть аналогичный базовый случай для обработки входных данных, которые меньше или равны 1. Затем мы запускаем цикл while, пока длина нашего fib_sequence не станет больше n. На каждой итерации цикла мы добавляем новое значение в наш массив fib_sequence, сумму: fib_sequence[-1] + fib_sequence[-2]. Это только два самых последних элемента в массиве, которые создают наше новое число Фибоначчи. Когда мы выходим из цикла, мы просто возвращаем последнее число в массиве.

Как вы можете видеть на выходе алгоритмов, когда передается вход 10, мы получаем обратно 10-е число Фибоначчи - оба алгоритма возвращают 55. У нас есть два пути решения проблемы.

Итерация против рекурсии

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

В приведенном выше примере я спрашиваю алгоритм для 35-го числа Фибоначчи. Посмотрите на затраченное время, наше итеративное решение дает нам это за 0,00002 секунды - очень хорошо! Однако наше рекурсивное решение занимает 5,698 секунды - практически вечность вычислительного времени! Как два простых решения довольно простой проблемы могут так сильно отличаться по производительности?

Вот еще одно рекурсивное дерево Фибоначчи - на этот раз для fib(7). Это ведет себя так же, как и раньше, но если вы присмотритесь, обнаруживается много дублирования. Например, fib(4) вызывается 3 раза, fib(3) 5 раз и fib(2) 8 раз. Когда мы просим еще большие числа, такие как fib(35), эта проблема растет экспоненциально - мы вызываем еще больше ненужных функций, которые сильно влияют на производительность. Выполнение fib(35) с использованием нашего рекурсивного решения приводит к 29,860,703 вызовам функций! Нелепо! Это показывает, насколько масштабируемым является это рекурсивное решение в его текущей реализации. Есть способы справиться с этим с помощью мемоизации, о которой, вероятно, стоит посвятить отдельную статью.

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

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

До скорого.