Поняття рекурсії

1.1 Визначення рекурсії та її основні концепції.

Рекурcія — це коли щось робить саму себе знову і знову. Уяви, що у тебе є інструкція, і частина цієї інструкції каже слідувати самій інструкції. Це, наче ти дав команду повторити саму команду.

Приклади з реального життя:

Дзеркала навпроти один одного:

Уяви, що ти стоїш між двома дзеркалами. Ти бачиш своє відображення, і у відображенні теж бачиш своє відображення, і так продовжується знову і знову. Це приклад рекурсії, тому що кожне дзеркало показує відображення іншого дзеркала.

Матрьошки:

Матрьошка — це лялька, всередині якої є інша лялька, а всередині тієї — ще одна, і так далі. Коли ти доходиш до найменшої ляльки, далі розкривати нічого. Це як базовий випадок у рекурсії — момент, коли зупинитися.

Поділ піци:

Уяви, що ти ділиш піцу навпіл. Потім ти береш одну половину і знову ділиш її наполовину, і так продовжуєш, поки шматочки не стануть занадто маленькими, щоб їх ділити. Поділ на частини — це рекурсивний процес, а момент, коли ти більше не можеш ділити шматочок, — це базовий випадок.

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

Як це працює?

Щоб зрозуміти рекурсію, потрібно знати два основних поняття:

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

Чому це корисно?

Рекурсія допомагає вирішити складні завдання, розбиваючи їх на більш прості частини. Замість того щоб вирішувати все завдання відразу, ти вирішуєш його по шматочкам.

Інші приклади з життя:

Казка в казці:

Уяви, що герой казки розповідає іншу казку, а герой тієї казки починає розповідати ще одну казку. Коли одна з казок закінчується, ти повертаєшся до попередньої казки. Базовий випадок — це коли закінчується остання казка.

Рекурсивний малюнок:

Ти малюєш великий трикутник, а потім у кожному куті цього трикутника малюєш маленький трикутник, і так продовжуєш, поки трикутники не стануть занадто маленькими. Базовий випадок — це коли трикутник стає настільки маленьким, що його не можна малювати.

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