Рекурсия в Python

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

В программировании под рекурсией понимается такая функция, которая вызывает саму себя.

Но если вы напишите функцию,которая будет вызывать саму себя бесконечное количество раз, получите ошибку Recursionerror: maximum recursion depth exceeded. Попробуйте запустить у себя на компьютере следующую программу.

def rec(x):
    print(x)
    rec(x+1)

rec(1)

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

def rec(x):
    if x<4:
        print(x)
        rec(x+1)
        print(x)

rec(1)

Условие выхода называют также базовым случаем - самым простым решением какой-нибудь задачи.

Нахождение факториала с помощью рекурсии

Например, базовым случаем (самым простым случаем) нахождения факториала, является 1! или 0!. Это значение гораздо легче найти, чем например 7! (факториал 7).

Но рекурсии кроме базового случая должен присутствовать рекурсивный случай или шаг рекурсии - это способ сведения задачи к более простой. Например, 5! = 1_*2_*3_*4_*5 = 4!_*5. То есть, чтобы найти факториал пяти, достаточно знать факториал четырех и умножить это на 5. Тогда в общем виде рекурентная формула нахождения факториала будет выглядеть следующим образом:

А код реализации будет следующим:

def fact(x):
    if x == 1 or x == 0:
        return 1
    return fact(x - 1) * x

a = int(input())
print(fact(a))

Нахождение чисел Фибоначчи

Числа Фибоначчи представляют собой рекурентный ряд чисел - это значит, что в этом ряду должны быть обязательно первые члены ряда (обычно это 0 и 1), а все остальные числа находятся от предыдущих путем сложения двух чисел стоящих перед текущим.

В итоге получаем такой ряд: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и т.д.

У каждого числа в этом ряду есть свой порядковый номер, начинается нумерация с единицы. И давайте обозначим за F(n) - n-ое число Фибоначчи. И тогда,чтобы найти пятое число Фибоначчи нужно сложить два предыдущих к нему F(5) = F(4)+F(4). А общая формула нахождения будет выглядеть следующим образом:

Ниже приведена реализация этой формулы в Python. Более подробно о том, как реализован этот алгоритм, смотрите в видео.

Проверить строку на палиндром(рекурсия)

Палиндром - слово или фраза, которые одинаково читаются слева направо и справа налево.

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

А для всех остальных строк мы будет брать первый и последний символ, если они совпадают, то рекурсивно будет проверять строку без этих символов, а в противном случае строка не является палиндромом.

Ниже представлена рекурсивная функция, которая реализует проверку на палиндром.

def palindrom(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return palindrom(s[1:-1])

a = input()
print(palindrom(a))