Книга: Введение в Python

Рекурсия

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

Напомним, что факториалом числа, например, 5 является произведение всех натуральных (целых) чисел от 1 до 5. То есть, 1 * 2 * 3 * 4 * 5

Рекурсивная функция вычисления факториала на языке Python будет выглядеть так:

| def fact(num):
| if num == 0:
| return 1# По договоренности факториал нуля равен единице
| else:
| return num * fact(num - 1)
| # возвращаем результат произведения num и результата возвращенного функцией fact(num - 1)

Однако следует помнить, что использование рекурсии часто может быть неоправданным. Дело в том, что в момент вызова функции в оперативной памяти компьютера резервируется определенное количество памяти, соответственно чем больше функций одновременно мы запускаем - тем больше памяти потребуется, что может привести к переполнению стека (stack overflow) и программа завершится аварийно, не так как предполагалось. Учитывая это, там где это возможно, вместо рекурсии лучше применять циклы.

Оглавление книги