Wprowadzenie do rekurencji w Pythonie

Czy chcesz zgłębić tajniki rekurencji w programowaniu? Ten przewodnik po rekurencji w Pythonie będzie dla Ciebie doskonałym startem.

Rekurencja jest wyjątkowo przydatnym narzędziem w arsenale programisty, umożliwiającym rozwiązywanie problemów. Chociaż na początku może wydawać się skomplikowana, w rzeczywistości pozwala tworzyć bardziej zgrabne i eleganckie rozwiązania dla trudnych zadań.

W tym samouczku, korzystając z języka Python, nauczymy się rekurencji w praktyczny sposób, poprzez analizę kodu. Szczegółowo omówimy:

• Podstawowe zasady rekurencji
• Działanie funkcji rekurencyjnych
• Implementację rekurencji w Pythonie
• Różnice między podejściem iteracyjnym a rekurencyjnym

Zaczynajmy!

Czym jest rekurencja?

Rekurencja to technika programistyczna, w której funkcja wywołuje samą siebie, aby rozwiązać zadany problem.

U jej podstaw leży idea dzielenia skomplikowanego problemu na mniejsze, identyczne podproblemy. Innymi słowy, problem rozwiązujemy poprzez odwołanie się do prostszych wersji tego samego problemu.

Jak zatem zaimplementować rekurencję w kodzie? Przyjrzyjmy się bliżej, jak działają funkcje rekurencyjne.

Zrozumienie funkcji rekurencyjnych

Funkcję rekurencyjną definiujemy jako taką, która w swoim ciele zawiera wywołanie samej siebie. Każde takie wywołanie reprezentuje uproszczoną wersję pierwotnego problemu.

Aby rekurencja miała szansę na zakończenie, funkcje rekurencyjne muszą zawierać co najmniej jeden przypadek bazowy – warunek, który powoduje, że funkcja przestaje się wywoływać i zwraca wynik.

Przeanalizujmy to dokładniej. Funkcja rekurencyjna składa się z:

• Przypadek bazowy: Jest to warunek (lub warunki) określający moment, w którym rekurencja powinna się zatrzymać. Po spełnieniu tego warunku funkcja zwraca wynik, bez dalszych wywołań rekurencyjnych. Przypadek bazowy jest niezbędny do zapobiegania niekończącej się rekurencji.
• Przypadek rekurencyjny: W tej części funkcji problem jest dzielony na mniejsze podproblemy. Funkcja wywołuje samą siebie, ale z zmodyfikowanymi danymi wejściowymi. Każde wywołanie rekurencyjne to krok w kierunku osiągnięcia przypadku bazowego.

Teraz omówimy, co dzieje się podczas wywołania funkcji rekurencyjnej.

Jak działa rekurencja „pod maską”?

Gdy funkcja jest wywoływana, na stosie wywołań umieszczane jest tzw. „ramka”, która przechowuje informacje o kontekście jej wykonania. Ramka ta zawiera argumenty funkcji, zmienne lokalne i adres powrotu (miejsce w kodzie, do którego program ma wrócić po zakończeniu funkcji).

W przypadku funkcji rekurencyjnych, każde wywołanie samej siebie powoduje umieszczenie nowej ramki na stosie, co wstrzymuje wykonanie poprzedniej. Stos umożliwia Pythonowi śledzenie wszystkich oczekujących wywołań funkcji, w tym wywołań rekurencyjnych.

Rekurencja trwa, dopóki nie zostanie osiągnięty przypadek bazowy. Gdy przypadek bazowy zwróci wynik, wywołania funkcji są rozwijane w odwrotnej kolejności – każda funkcja zwraca wynik do poziomu stosu wyżej. Proces ten trwa aż do zakończenia pierwotnego wywołania funkcji.

Implementacja rekurencji w Pythonie

W tej części przyjrzymy się trzem prostym przykładom rekurencji:

• Obliczanie silni liczby
• Obliczanie wyrazów ciągu Fibonacciego
• Implementacja wyszukiwania binarnego za pomocą rekurencji

Dla każdego przykładu sformułujemy problem, przedstawimy jego rekurencyjną implementację w Pythonie i wyjaśnimy sposób jej działania.

#1. Obliczanie silni przy użyciu rekurencji

Zadanie: Oblicz silnię nieujemnej liczby całkowitej n, oznaczonej jako n!. Matematycznie silnia liczby n jest iloczynem wszystkich liczb całkowitych od 1 do n.

Obliczenie silni idealnie nadaje się do rekurencyjnej implementacji:

Oto rekurencyjna funkcja obliczająca silnię liczby n:

def factorial(n):
	# Przypadek bazowy
    if n == 0 or n == 1:
        return 1
	# Przypadek rekurencyjny: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Obliczmy 5! używając funkcji `factorial()`:

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

Zobaczmy, jak ta funkcja działa:

• Mamy przypadek bazowy, który sprawdza, czy n jest równe 0 lub 1. Jeśli warunek jest spełniony, funkcja zwraca 1. Pamiętamy, że 0! wynosi 1, podobnie jak 1!.
• Jeśli n jest większe od 1, obliczamy n! mnożąc n przez silnię z (n-1). Wyraża się to jako `n * factorial(n – 1)`.
• Funkcja wykonuje wywołania rekurencyjne z malejącymi wartościami n, dopóki nie zostanie osiągnięty przypadek bazowy.

#2. Ciąg Fibonacciego z rekurencją

Problem: Znajdź wyraz o indeksie n w ciągu Fibonacciego. Ciąg Fibonacciego definiuje się następująco: F(0) = 0, F(1) = 1 i F(n) = F(n-1) + F(n-2) dla n >= 2.

def fibonacciSeq(n):
	# Przypadki bazowe
    if n == 0:
        return 0
    elif n == 1:
        return 1
	# Rekurencja: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Uruchommy funkcję:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Wynik: 5

Oto jak działa ta funkcja:

• Zaczynamy od przypadków bazowych. Jeśli n wynosi 0, funkcja zwraca 0. Jeśli n wynosi 1, zwraca 1. Pamiętamy, że F(0) = 0 i F(1) = 1.
• W przypadku rekurencyjnym, jeśli n jest większe od 1, funkcja oblicza F(n) dodając F(n-1) i F(n-2). Jest to wyrażone jako `fibonacciSeq(n – 1) + fibonacciSeq(n – 2)`.
• Funkcja wywołuje samą siebie z malejącymi wartościami n, aż osiągnie przypadki bazowe.

#3. Rekurencyjna implementacja wyszukiwania binarnego

Problem: Zaimplementuj algorytm wyszukiwania binarnego za pomocą rekurencji, aby znaleźć pozycję elementu docelowego na posortowanej liście.

Oto rekurencyjna implementacja wyszukiwania binarnego:

def binarySearch(arr, target, low, high):
	# Przypadek bazowy: cel nie został znaleziony
    if low > high:
        return -1

    mid = (low + high) // 2

	# Przypadek bazowy: cel został znaleziony
    if arr[mid] == target:
        return mid
	# Przypadek rekurencyjny: przeszukaj lewą lub prawą połowę tablicy
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

Funkcja `binarySearch` dzieli interwał wyszukiwania na pół przy każdym wywołaniu rekurencyjnym, aż znajdzie cel lub stwierdzi, że nie ma go na liście.

Oto przykład użycia funkcji:

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

Przeanalizujmy działanie funkcji:

• W rekurencyjnej implementacji wyszukiwania binarnego mamy dwa przypadki bazowe. Po pierwsze, jeśli wartość `low` staje się większa od wartości `high`, oznacza to, że szukany element nie znajduje się na liście. Zwracamy wtedy -1, sygnalizując, że celu nie znaleziono.
• Drugi przypadek bazowy sprawdza, czy element w środkowym indeksie bieżącego przedziału wyszukiwania jest równy szukanemu celowi. Jeśli tak, zwracamy środkowy indeks, informując, że cel został znaleziony.
• W przypadku rekurencyjnym, jeśli środkowy element jest większy od celu, rekurencyjnie przeszukujemy lewą połowę tablicy, wywołując `binarySearch(arr, target, low, mid – 1)`. Jeśli środkowy element jest mniejszy od celu, szukamy w prawej połowie, wywołując `binarySearch(arr, target, mid + 1, high)`.

Podejście rekurencyjne a iteracyjne

Podejście iteracyjne – wykorzystujące pętle – to alternatywna metoda rozwiązywania problemów. Czym zatem różni się ono od rekurencji? Sprawdźmy.

Najpierw porównamy rekurencyjne i iteracyjne rozwiązania dla tego samego problemu: obliczania silni liczby.

Oto rekurencyjna implementacja silni:

def factorialRec(n):
	# Przypadek bazowy
    if n == 0 or n == 1:
        return 1
	# Przypadek rekurencyjny: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Wiemy, że silnia liczby nieujemnej jest iloczynem wszystkich liczb od 1 do n, możemy też napisać iteracyjną implementację za pomocą pętli:

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

Obie implementacje dają identyczne wyniki:

factorial_5 = factorialRec(5)
print(factorial_5)
# Wynik: 120

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

Czy podejście iteracyjne jest lepsze od rekurencji? W przypadku bardzo głębokiej rekurencji – z dużą liczbą wywołań funkcji – mogą wystąpić błędy z powodu przepełnienia stosu. Pętla jest lepszą opcją w problemach, w których rekurencyjna implementacja wymaga zbyt wielu wywołań funkcji, aby osiągnąć przypadek bazowy.

Podsumujmy różnice między implementacjami iteracyjnymi i rekurencyjnymi:

Cecha	Podejście rekurencyjne	Podejście iteracyjne
Struktura	Wykorzystuje rekurencyjne wywołania funkcji i opiera się na stosie wywołań.	Wykorzystuje pętle do iteracji, bez dodatkowych wywołań funkcji.
Przypadki bazowe	Wymaga jawnych przypadków bazowych, aby zatrzymać rekurencję.	Zazwyczaj używa warunków pętli do zakończenia.
Wydajność	Może być mniej wydajne pod względem pamięci ze względu na stos wywołań. Głęboka rekurencja może czasami prowadzić do błędów przepełnienia stosu.	Ogólnie bardziej wydajne pod względem pamięci i mniej podatne na błędy przepełnienia stosu.
Debugowanie	Może być trudne do debugowania ze względu na wiele wywołań funkcji i zagnieżdżone konteksty wykonania.	Zwykle łatwiejsze do debugowania ze względu na prosty, liniowy przepływ wykonywania.

Podsumowanie

W tym artykule zaczęliśmy od zdefiniowania rekurencji oraz omówienia, jak tworzyć funkcje rekurencyjne za pomocą przypadków bazowych i reguł rekurencyjnych.

Następnie przeszliśmy do praktyki, pisząc w Pythonie rekurencyjne implementacje dla typowych problemów programistycznych. Na koniec omówiliśmy różnice pomiędzy podejściem iteracyjnym i rekurencyjnym oraz zalety i wady każdego z nich.

Teraz zapoznaj się z listą pytań rekrutacyjnych dotyczących Pythona.