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

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

Рекурсія — надзвичайно корисна техніка вирішення проблем, яку можна додати до інструментарію програміста. Хоча спочатку часто важко подумати, рекурсія може допомогти вам знайти елегантніші рішення складних проблем.

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

• Основи рекурсії
• Рекурсивні функції та як вони працюють
• Реалізація рекурсивних функцій на Python
• Відмінності між ітеративним і рекурсивним підходами до вирішення проблем

Давайте розпочнемо!

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

Рекурсія — це техніка програмування, коли функція викликає саму себе неодноразово для вирішення проблеми.

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

Отже, як реалізувати рекурсію в коді? Для цього давайте розберемося, як працюють рекурсивні функції.

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

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

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

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

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

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

Як рекурсія працює під капотом

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

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

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

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

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

Обчислення факторіала числа

Обчислення чисел Фібоначчі

Реалізація бінарного пошуку за допомогою рекурсії.

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

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

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

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

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

def factorial(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Давайте обчислимо 5! за допомогою функції factorial():

factorial_5 = factorial(5)
print(factorial(5))
# Output: 120

Тепер подивимося, як працює функція:

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

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

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

def fibonacciSeq(n):
	# Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
	# Recursion: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Давайте запустимо функцію:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Output: 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):
	# Base case: target not found
    if low > high:
        return -1

    mid = (low + high) // 2

	# Base case: target found
    if arr[mid] == target:
        return mid
	# Recursive case: search left or right half of the array
    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)
# Output: 4

Давайте розберемо, що робить функція:

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

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

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

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

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

def factorialRec(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: 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)
# Output: 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Output: 120

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

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

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

Висновок

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

Потім ми написали код на Python — рекурсивну реалізацію поширених проблем програмування. Нарешті, ми дізналися про відмінності між ітеративним і рекурсивним підходами, а також про плюси і мінуси кожного з цих підходів.

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