Понятие рекурсии

Видео на Vimeo

---

1.1 Определение рекурсии и её основные концепции

Рекурсия — это когда что-то делает само себя снова и снова. Представь, что у тебя есть инструкция, и часть этой инструкции говорит следовать самой инструкции. Это, как если бы ты дал команду повторить саму команду.

Примеры из реальной жизни:

Зеркала напротив друг друга:

Представь, что ты стоишь между двумя зеркалами. Ты видишь своё отражение, и в отражении тоже видишь своё отражение, и так продолжается снова и снова. Это пример рекурсии, потому что каждое зеркало показывает отражение другого зеркала.

Матрёшки:

Матрёшка — это кукла, внутри которой есть другая кукла, а внутри той — ещё одна, и так далее. Когда ты добираешься до самой маленькой куклы, дальше раскрывать нечего. Это как базовый случай в рекурсии — момент, когда остановиться.

Разделение пиццы:

Представь, что ты делишь пиццу пополам. Затем ты берёшь одну половину и снова делишь её пополам, и так продолжаешь, пока кусочки не станут слишком маленькими, чтобы их делить. Деление на части — это рекурсивный процесс, а момент, когда ты больше не можешь делить кусочек, — это базовый случай.

Важно! Рекурсия – это не бесконечное повторение команды, тут речь скорее о том, что при делении сложной задачи на части, подход к решению частей задачи аналогичен решению всей задачи.

Как это работает?

Чтобы понять рекурсию, нужно знать два основных понятия:

• Базовый случай: это условие, при котором рекурсия прекращается. Например, в примере с матрёшками базовый случай — это когда ты открываешь самую маленькую матрёшку, и внутри уже ничего нет.
• Рекурсивный случай: это когда задача повторяется с меньшими частями. В примере с пиццей ты делишь кусок, а затем делишь половинку и так далее.

Почему это полезно?

Рекурсия помогает решить сложные задачи, разбивая их на более простые части. Вместо того чтобы решать всю задачу сразу, ты решаешь её по кусочкам.

Другие примеры из жизни:

Сказка в сказке:

Представь, что герой сказки рассказывает другую сказку, а герой той сказки начинает рассказывать ещё одну сказку. Когда одна из сказок заканчивается, ты возвращаешься к предыдущей сказке. Базовый случай — это когда заканчивается последняя сказка.

Рекурсивный рисунок:

Ты рисуешь большой треугольник, а затем в каждом углу этого треугольника рисуешь маленький треугольник, и так продолжаешь, пока треугольники не станут слишком маленькими. Базовый случай — это когда треугольник становится настолько маленьким, что его нельзя рисовать.

1.2 Базовый случай: определение и примеры

Базовый случай — это условие, которое прекращает рекурсивные вызовы и позволяет функции вернуть конкретное значение. Обычно это самое простое и очевидное решение задачи, которое не требует дальнейшей рекурсии.

Примеры базового случая:

Факториал числа:

Факториал числа n обозначается как F(n) == 1 * 2 * 3 * … * n. Так же очевидно, что F(n) == n * F(n-1).

Базовый случай: факториал числа 0 или 1 равен 1F(0) == F(1)==1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Базовый случай
    else:
        return n * factorial(n - 1)
        

Числа Фибоначчи:

Числа Фибоначчи – это последовательность: 1, 1, 2, 3, 5, 8, 13, …, где каждое следующее число является суммой двух предыдущих. Для F(n) == F(n-1) + F(n-2).

Базовый случай: первые два числа Фибоначчи равны 1, поэтому «нулевое» число Фибоначчи равно 0. Или F(0) = 0 и F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Базовый случай
    elif n == 1:
        return 1  # Базовый случай
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Рекурсивный случай: определение и примеры

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

Примеры рекурсивного случая:

Факториал числа:

Рекурсивный случай: факториал числа n равен n умножить на факториал числа n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Базовый случай
    else:
        return n * factorial(n - 1)  # Рекурсивный случай
        

Числа Фибоначчи:

Рекурсивный случай: F(n) равен сумме F(n-1) и F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Базовый случай
    elif n == 1:
        return 1  # Базовый случай
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Рекурсивный случай
        

1.4 Примеры рекурсивных алгоритмов

1. Обход бинарного дерева:

Пример обхода в порядке "in-order".

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Пример использования:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Поиск максимального элемента в списке:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Базовый случай
    else:
        max_of_rest = find_max(lst[1:])  # Рекурсивный случай
        return max(lst[0], max_of_rest)
        
# Пример использования:
print(find_max([1, 5, 3, 9, 2]))  # Вывод: 9
        
        

3. Рекурсивный бинарный поиск:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Базовый случай: элемент не найден
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Базовый случай: элемент найден
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Рекурсивный случай
    else:
        return binary_search(arr, target, left, mid - 1)  # Рекурсивный случай 
# Пример использования:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Вывод: 4