Рекурсия¶

Рекурсия - очень важное понятие функционального программирования.
Центральное понятие рекурсии - самореференция, то есть, когда функции вызывают сами себя. Используется для решения проблем, которые могут быть разбиты на более легкие подзадачи того же типа.

Классическим примером функции, реализуемой рекурсивно, является функция вычисления факториала, которая находит результат умножения всех натуральных чисел ниже заданного числа.
Например: 5! (факториал числа 5) означает 5 * 4 * 3 * 2 * 1 (120). Чтобы реализовать это рекурсивно, помните, что 5! = 5 * 4!, 4! = 4 * 3!, 3! = 3 * 2! и так далее. При этом, n! = n * (n-1)!.
Кроме того, 1! = 1. Это известно как базовый случай, так как он не требует вычисления каких-либо других факториалов.
Ниже приводится рекурсивное выполнение функции факториала.

def factorial(x):
    if x == 1:
        return 1
    else:
        return x * factorial(x-1)

print(factorial(5))

Базовый случай действует как команда выхода из рекурсии.

Рекурсивные функции, как и бесконечные циклы while, также могут выполнятся бесконечно. Так случится, если вы забудете реализовать базовый случай.
Ниже приводится неправильно записанная функция факториала. Так как не реализован базовый вариант, она будет выполняться, пока у интерпретатора не закончится память, после чего случится аварийное завершение.

def factorial(x):
    return x * factorial(x-1)

print(factorial(5))

Запустите код и посмотрите, как всё работает!

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

Пример:

def is_even(x):
    if x == 0:
        return True
    else:
        return is_odd(x-1)

def is_odd(x):
    return not is_even(x)

print(is_odd(17))
print(is_even(23))