Вступ до рекурсії в Python

Автор

Бажаєте глибше зрозуміти рекурсію в програмуванні? Цей посібник з рекурсії в Python допоможе вам розпочати.

Рекурсія – це потужний метод розв’язання задач, який може збагатити інструментарій будь-якого програміста. Хоча на початку її концепція може здаватися складною, рекурсія відкриває шлях до елегантних рішень для багатьох непростих проблем.

В цьому навчальному матеріалі ми вивчимо рекурсію через призму коду на Python. Зокрема, ми розглянемо:

  • Основи рекурсії.
  • Принцип роботи рекурсивних функцій.
  • Практичну реалізацію рекурсивних функцій на Python.
  • Порівняння ітеративного та рекурсивного підходів до розв’язання задач.

Тож почнімо!

Що таке рекурсія?

Рекурсія – це техніка програмування, де функція викликає саму себе, повторюючи цей процес для розв’язання задачі.

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

Як же впровадити рекурсію в коді? Розгляньмо детальніше принцип дії рекурсивних функцій.

Розуміння рекурсивних функцій

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

Для забезпечення завершення рекурсії, рекурсивні функції повинні мати один або декілька базових випадків – умов, за яких функція припиняє самовиклики та повертає результат.

Розглянемо це детальніше. Рекурсивна функція включає:

  • Базовий випадок: це умова (або умови), що визначають момент, коли рекурсія повинна зупинитися. При досягненні базового випадку функція повертає результат без подальших рекурсивних викликів. Базовий випадок необхідний для запобігання нескінченній рекурсії.
  • Рекурсивний випадок: він визначає, як розбити задачу на менші підзадачі. У цій частині функції відбувається її самовикликання, але з модифікованими вхідними даними. Таким чином, кожне рекурсивне звернення наближає нас до базового випадку.

Далі ми розглянемо, що відбувається, коли викликається рекурсивна функція.

Як рекурсія працює зсередини

При виклику функції запис про її виконання додається до стеку викликів. Цей запис містить інформацію про аргументи функції, локальні змінні та адресу повернення після завершення виконання.

У випадку рекурсивних функцій, коли функція викликає сама себе, новий запис додається до стеку викликів, призупиняючи поточне виконання. Стек дозволяє Python відстежувати всі незавершені виклики, включно з рекурсивними.

Рекурсія продовжується доти, доки не буде досягнуто базового випадку. Після повернення результату базовим випадком, виклики функцій розгортаються в зворотному порядку, де кожна функція повертає свій результат на попередній рівень стеку викликів. Цей процес триває до завершення початкового виклику.

Реалізація рекурсії в Python

У цьому розділі розглянемо три прості приклади застосування рекурсії:

  • Обчислення факторіалу числа.
  • Генерування чисел Фібоначчі.
  • Реалізація бінарного пошуку за допомогою рекурсії.

Для кожного прикладу ми спочатку сформулюємо задачу, потім представимо рекурсивну реалізацію на Python, і нарешті пояснимо, як вона працює.

#1. Обчислення факторіалу за допомогою рекурсії

Задача: обчислити факторіал невід’ємного цілого числа n, що позначається як n!. Факторіал числа n є добутком усіх натуральних чисел від 1 до n.

Обчислення факторіалу ідеально підходить для рекурсивного підходу, як показано далі:

Ось рекурсивна функція для обчислення факторіалу:

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

Обчислимо 5! за допомогою функції `factorial()`:

factorial_5 = factorial(5)
print(factorial(5))
# Вивід: 120

Розгляньмо принцип роботи цієї функції:

  • Базовий випадок перевіряє, чи n дорівнює 0 або 1. Якщо умова виконується, функція повертає 1. Нагадуємо, що 0! дорівнює 1, так само як і 1!.
  • Якщо n більше 1, то n! обчислюється як добуток n на факторіал від n-1. Це виражається як `n * factorial(n – 1)`.
  • Функція продовжує робити рекурсивні виклики зі зменшеними значеннями n, поки не досягне базового випадку.

#2. Числа Фібоначчі з рекурсією

Задача: знайти n-й член у послідовності Фібоначчі. Послідовність Фібоначчі визначається так: F(0) = 0, F(1) = 1 і F(n) = F(n-1) + F(n-2) для n >= 2.

def fibonacciSeq(n):
    # Базові випадки
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Рекурсія: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Запустимо функцію:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Вивід: 5

Ось як працює ця функція:

  • Спочатку розглянемо базові випадки. Якщо n дорівнює 0, повертається 0. Якщо n дорівнює 1, повертається 1. Нагадаємо, що F(0) = 0 і F(1) = 1.
  • У рекурсивному випадку, якщо n більше 1, функція обчислює F(n), додаючи F(n-1) та F(n-2). Це виражається як `fibonacciSeq(n – 1) + fibonacciSeq(n – 2)`.
  • Функція продовжує робити рекурсивні виклики зі зменшенням значень n, доки не досягне базових випадків.

#3. Рекурсивна реалізація бінарного пошуку

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

Ось рекурсивна реалізація бінарного пошуку:

def binarySearch(arr, target, low, high):
    # Базовий випадок: ціль не знайдено
    if low > high:
        return -1

    mid = (low + high) // 2

    # Базовий випадок: ціль знайдено
    if arr[mid] == target:
        return mid
    # Рекурсивний випадок: пошук у лівій або правій половині масиву
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

Функція `binarySearch` розділяє інтервал пошуку навпіл з кожним рекурсивним викликом, доки не знайде цільовий елемент або не визначить, що його немає в списку.

Ось приклад використання функції:

arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# Вивід: 4

Розберемо принцип роботи функції:

  • В рекурсивній реалізації бінарного пошуку є два базові випадки. По-перше, якщо `low` стає більшим за `high`, це означає, що цільового елемента немає в списку. Тому повертаємо -1, щоб позначити, що ціль не знайдено.
  • Другий базовий випадок перевіряє, чи елемент із середнім індексом у поточному інтервалі пошуку дорівнює цільовому. Якщо вони збігаються, повертаємо індекс середини, що вказує на те, що ми знайшли ціль.
  • У рекурсивному випадку, якщо середній елемент більший за цільовий, рекурсивно шукаємо ліву половину масиву, викликаючи `binarySearch(arr, target, low, mid – 1)`. Якщо середній елемент менший за цільовий, шукаємо праву половину, викликаючи `binarySearch(arr, target, mid + 1, high)`.

Рекурсивний проти ітеративного підходу

Ітеративний підхід – використання циклів – є ще одним поширеним методом розв’язання задач. У чому його відмінність від рекурсії? Давайте розберемось.

Перш за все, порівняємо рекурсивні та ітеративні рішення для загальної задачі: обчислення факторіалу числа.

Ось рекурсивна реалізація обчислення факторіалу:

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

Оскільки ми знаємо, що факторіал невід’ємного числа є добутком усіх чисел від 1 до n, ми також можемо реалізувати ітеративну версію з використанням циклів.

def factorialIter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Обидві ці реалізації повертають ідентичні результати.

factorial_5 = factorialRec(5)
print(factorial_5)
# Вивід: 120

factorial_5 = factorialIter(5)
print(factorial_5)
# Вивід: 120

Чи означає це, що ітеративний підхід кращий за рекурсивний? У випадках глибокої рекурсії – з надто великою кількістю викликів функцій – можна зіткнутися з помилками через перевищення глибини рекурсії. Цикл є кращим варіантом для задач, рекурсивна реалізація яких вимагає надто багато викликів функцій для досягнення базового випадку.

Підсумуємо відмінності між ітеративними та рекурсивними реалізаціями:

Характеристика Рекурсивний підхід Ітеративний підхід
Структура Використовує рекурсивні виклики функцій і покладається на стек викликів. Використовує цикли для ітерації без додаткових викликів функцій.
Базові випадки Потребує явних базових випадків для зупинки рекурсії. Зазвичай використовує умови циклу для завершення.
Продуктивність Може бути менш ефективним з точки зору використання пам’яті через стек викликів. Глибока рекурсія іноді може призводити до помилок переповнення стеку. Зазвичай ефективніше використовує пам’ять та менш схильний до помилок переповнення стеку.
Налагодження Може бути складним для налагодження через численні виклики функцій та вкладені контексти виконання. Зазвичай легше налагоджувати завдяки прямому лінійному потоку виконання.

Висновок

У цій статті ми розглянули визначення рекурсії, принципи побудови рекурсивних функцій з базовими випадками та рекурентними відношеннями.

Ми також написали рекурсивні реалізації на Python для поширених задач програмування. Насамкінець ми вивчили відмінності між ітеративним та рекурсивним підходами, а також переваги та недоліки кожного з них.

Для подальшого вивчення радимо переглянути цей список питань для співбесіди з Python.