Рекурсія в Python

Рекурсія — це процес визначення чогось у межах самого себе. Прикладом у фізичному світі може бути розміщення двох дзеркал одне напроти одного. Будь-який об’єкт між ними відображатиметься рекурсивно.

Рекурсивна функція в 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