В данной статье хочу рассмотреть примеры использования рекурсии для решения некоторых задач на Python.
Рекурсия — вызов функции (процедуры) из неё же самой, до завершения первоначального вызова функции.
Факториал
Описание:
Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно: 5! = 5*4*3*2*1 = 120
def Fact(n): assert n >= 0, 'Факториал не определен' # assert это оператор, который проверяет условие и вызывает ошибку, если условие ложно if n == 0: return 1 return Fact(n-1)*n print(Fact(5))
120
Алгоритм Евклида
Описание:
Определение наибольшего общего делителя.
Примечание: В модуле math языка программирования Python есть функция gcd(), вычисляющая наибольший общий делитель двух чисел.
def gcd(a, b): if a == b: return a elif a > b: return gcd(a - b, b) else: return gcd(a, b - a) print(gcd(30, 18)) # 2 вариант: def gcd1(a, b): if b == 0: return a return gcd(b, a % b) print(gcd1(30, 18))
6 6
Числа Фиббоначи
Описание:
Функция, которая находит число Фиббоначи по его номеру.
Последовательность Фибоначчи начинается с 1 и 1, после чего каждое новое число является результатом сложения двух предыдущих чисел: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
def fib(n): if n == 1 or n == 2: return 1 return fib(n - 1) + fib(n - 2) print(fib(7))
13
Возведение в положительную и отрицательную степень
Возведение в положительную степень с помощью рекурсии:
def power(n, m): if m == 0: return 1 x = power(n, m-1) return n*x print(power(2, 3))
8
Возведение в отрицательную степень с помощью рекурсии:
def powerMin(n, m): if m == 0: return 1 x = powerMin(n, m+1) return 1/n*x print(powerMin(2, -3))
0.125
Сумма последовательности
Функция, которая с помощью рекурсии считает сумму последовательности с шагом m.
В качестве аргументов подаются целые положительные числа n (последний элемент последовательности) и m (шаг последовательности).
def sum_of_seq(n, m): if n == 1: return 1 elif n < 1: return 0 x = sum_of_seq(n-m, m) return n + x print(sum_of_seq(7, 1)) print(sum_of_seq(6, 9)) print(sum_of_seq(5, 2))
28 6 9