Рекурсия
Рассмотрим задачу получения факториала числа. В математике он обозначается '!' и функция факториала описывается так:
- 0! = 1.
- n! = 1 * 2 * ... * n, n > 0.
Напишем функцию, вычисляющую факториал числа n.
def fact(n):
factorial = 1
for i in range(2, n + 1):
factorial *= i
return factorial
print(fact(5))Давайте немного перепишем определение факториала:
Мы видим, что для вычисления n! нам нужно найти (n - 1)! и умножить результат на n. Таким образом, мы используем функцию для вычисления нового значения функции. Функции, в которых происходит вызов самих этих функций, называют рекурсивными.
Давайте напишем рекурсивную функцию для вычисления факториала. При создании рекурсивных функций необходимо:
- 0! = 1.
- n! = (1 * 2 * ... * (n - 1)) *n = (n - 1)! * n.
Мы видим, что для вычисления n! нам нужно найти (n - 1)! и умножить результат на n. Таким образом, мы используем функцию для вычисления нового значения функции. Функции, в которых происходит вызов самих этих функций, называют рекурсивными.
Давайте напишем рекурсивную функцию для вычисления факториала. При создании рекурсивных функций необходимо:
- Написать, что вернёт функция при начальном значении аргумента.
- Написать правило получения нового значения на основе уже вычисленных на предыдущих шагах.
def fact(n):
if n == 0: # 0! = 1
return 1
return fact(n - 1) * n # n! = (n - 1)! * n
print(fact(5))Вывод программы:
120
120
Обратите внимание на то, что рекурсивный вариант функции выполняет действия, которые описаны правилом вычисления факториала. Такой стиль программирования называется декларативным. Данный подход описывает сам результат. Функции, которые мы писали ранее, основаны на императивном стиле и отвечают на вопрос о способе получения результата.
Рассмотрим применение рекурсивной функции для вычисления n-го числа последовательности Фибоначчи. Числа Фибоначчи — последовательность чисел, вычисляемых по следующему правилу:
Программа с рекурсивной функцией вычисления n-го числа Фибоначчи запишется так:
Рассмотрим применение рекурсивной функции для вычисления n-го числа последовательности Фибоначчи. Числа Фибоначчи — последовательность чисел, вычисляемых по следующему правилу:
- Первые два числа последовательности равны 1.
- n-е число Фибоначчи равно сумме двух предыдущих, то есть fib(n) = fib(n - 1) + fib(n - 2), где n - индекс числа последовательности.
Программа с рекурсивной функцией вычисления n-го числа Фибоначчи запишется так:
def fib(n):
if n in (0, 1):
return 1
return fib(n - 1) + fib(n - 2)
print(fib(35))