Автор оригинала: Pankaj Kumar.

Пример рекурсии Python – рекурсивные функции

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

Что такое рекурсия в Python?

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

Надо ли нам рекурсивные функции?

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

Но некоторые программисты предпочитают рекурсионные петли. Это вопрос выбора в основном, и вы свободны либо использовать петли, либо рекурсию.

Примеры функции рекурсии Python

Давайте посмотрим на пару примеров функции рекурсии в Python.

1. факториал целого числа

Факториал целого числа рассчитывается путем умножения целых чисел от 1 на этот номер. Например, факториал 10 будет 1 * 2 * 3 … * 10.

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

def factorial(n):
    result = 1

    for i in range(1, n + 1):
        result = result * i

    return result


print(f'Factorial of 10 = {factorial(10)}')
print(f'Factorial of 5 = {factorial(5)}')

Давайте посмотрим, как мы можем изменить функцию факториала () для использования рекурсии.

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


print(f'Factorial of 10 = {factorial(10)}')
print(f'Factorial of 5 = {factorial(5)}')

На следующем изображении показано выполнение рекурсивной функции.

2. Фибоначчи серия

Серия FIBONACCI – это последовательность чисел, где каждый номер является суммой двух предыдущих чисел. Например – 1, 1, 2, 3, 5, 8, 13, 21 и так далее.

Давайте посмотрим на функцию, чтобы вернуть номера серии FIBONACCI с использованием петлей.

def fibonacci(n):
    """ Returns Fibonacci Number at nth position using loop"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    i1 = 0
    i2 = 1
    num = 1
    for x in range(1, n):
        num = i1 + i2
        i1 = i2
        i2 = num
    return num


for i in range(10):
    print(fibonacci(i), end=" ")

# Output: 0 1 1 2 3 5 8 13 21 34 

Вот реализация функции FIBONACCI () с использованием рекурсии.

def fibonacci(n):
    """ Returns Fibonacci Number at nth position using recursion"""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


for i in range(10):
    print(fibonacci(i), end=" ")

# Output: 0 1 1 2 3 5 8 13 21 34 

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

Что такое базовый случай в рекурсии?

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

Вы можете проверить это поведение как в приведенных выше примерах. Рекурсивные аргументы вызова функции приближаются к базовому корпусу.

Преимущества рекурсии

• Иногда рекурсия уменьшает количество строк кода.
• Код рекурсии выглядит просто.
• Если мы знаем базовый случай, то использование рекурсии в функции проще.

Недостатки рекурсии

• Если нет реализован правильно, функция никогда не прекратится.
• Понимание рекурсии больше путаницы по сравнению с петлями.

Рекурсия или петли?

Это вопрос личного выбора. Я всегда предпочитаю петли по рекурсии. Я не видел никакого примера, где мы не можем использовать петли и должны использовать только рекурсию.

Рекомендации:

• Википедия