Рекурсия в Python / Ravesli

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

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

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

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

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

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

def factorial(x):
    """Это рекурсивная функция 
       нахождения факториала целого числа."""

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


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

def factorial(x):

"""Это рекурсивная функция

нахождения факториала целого числа."""

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() является рекурсивной функцией, поскольку она вызывает сама себя. Когда мы вызываем эту функцию с положительным целым числом, она будет рекурсивно вызывать себя, уменьшая число.

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

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

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

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

def recursor():
    recursor()
recursor()

def recursor():

recursor()

Результат:

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