Рекурсия Python

Рекурсия Python

В этом руководстве вы научитесь создавать рекурсивную функцию (функция, которая вызывает сама себя).

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

Рекурсия — это процесс определения чего-либо с точки зрения самого себя.

Примером физического мира может быть размещение двух параллельных зеркал друг против друга. Любой объект между ними будет отражен рекурсивно.

<час>

Рекурсивная функция Python

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

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

<рисунок>

Ниже приведен пример рекурсивной функции для нахождения факториала целого числа.

Факториал числа — это произведение всех целых чисел от 1 до этого числа. Например, факториал числа 6 (обозначается как 6!) равен 1*2*3*4*5*6 =720 . .

Пример рекурсивной функции

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

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


num = 3
print("The factorial of", num, "is", factorial(num))

Вывод

The factorial of 3 is 6

В приведенном выше примере factorial() является рекурсивной функцией, поскольку она вызывает сама себя.

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

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

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Давайте посмотрим на изображение, которое показывает пошаговый процесс того, что происходит:

<рисунок>

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

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

Интерпретатор Python ограничивает глубину рекурсии, чтобы избежать бесконечных рекурсий, приводящих к переполнению стека.

По умолчанию максимальная глубина рекурсии составляет 1000 . . Если предел превышен, это приводит к RecursionError . Давайте рассмотрим одно из таких условий.

def recursor():
    recursor()
recursor()

Вывод

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

<час>

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

1. Рекурсивные функции делают код чистым и элегантным.
2. Сложную задачу можно разбить на более простые подзадачи с помощью рекурсии.
3. Генерировать последовательность проще с помощью рекурсии, чем с использованием вложенных итераций.

<час>

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

1. Иногда трудно понять логику рекурсии.
2. Рекурсивные вызовы дороги (неэффективны), так как занимают много памяти и времени.
3. Рекурсивные функции трудно отлаживать.