Рекурсия - одна из самых сложных для понимания тем. Но, разобравшись в этой теме, можно открыть для себя массу возможностей. Тот, кто понимает рекурсию - владеет очень мощным инструментом.
Рекурсия — прием, когда функция может вызывать сама себя.
Для изучения рекурсии обычно используют задачу вычисления факториала числа N. Это 1*2*3*...*N. Так как в такой последовательности число N умножается на произведение всех чисел меньше N, факториал легко можно записать в рекурсивном виде:
Факториал(N) = N * Факториал(N-1)
Напишем функцию факториала на питоне:
Строка 3 - это точка выхода из рекурсии. Если число будет равно нулю, произойдёт выход, то есть функция вернет единицу. В противном случае будет выполняться 5 строка. Функция будет уходить "вглубь", как показано на схеме:
А уже "из глубины" обратно к "вершине", то есть числу 5, будет возвращаться результат (1 * 1 * 2 * 3 * 4 * 5).
Разберем другой пример.
Дано положительное число a и целое неотрицательное число n. Вычислите a^n не используя циклы, возведение в степень через ** и функцию math.pow(), а используя рекуррентное соотношение
a^n=a⋅a^(n-1).
Решение оформите в виде функции power(a, n).
Действительно, чтобы возвести 2 в 3-ю степень, нужно 2 * 2^2. А чтобы 2 возвести во 2-ю степень, нужно 2 * 2^1, и так далее до нуля. Как и в предыдущем примере, 3 строка - это точка выхода из рекурсии, а 5 строка - продолжение рекурсии.
И ещё один пример.
Дана последовательность целых чисел, заканчивающаяся числом 0. Выведите с помощью рекурсии эту последовательность в обратном порядке.
Входные данные:
Функция reverse() реагирует на число x, и если оно не равно нулю, продолжает запрашивать ввод, храня предыдущий результат в кэш-памяти. Строка 5 срабатывает только в самом конце, она и является выходом из рекурсии.
Задачи для самостоятельного решения.
1) Попробуйте рекурсивно вычислить длину списка.
2) Попробуйте рекурсивно перевернуть список.