Python recursion

В данной статье хочу рассмотреть примеры использования рекурсии для решения некоторых задач на 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