Wprowadzenie do rekurencji w Pythonie

Chcesz dowiedzieć się wszystkiego o rekurencji w programowaniu? Ten samouczek na temat rekurencji w Pythonie pomoże Ci zacząć.

Rekurencja to bardzo pomocna technika rozwiązywania problemów, którą można dodać do zestawu narzędzi programisty. Choć początkowo często trudno się o tym przekonać, rekurencja może pomóc w znalezieniu bardziej eleganckich rozwiązań złożonych problemów.

W tym samouczku zastosujemy podejście oparte na kodzie do nauki rekurencji przy użyciu języka Python. W szczególności omówimy:

Podstawy rekurencji
Funkcje rekurencyjne i ich działanie
Implementacja funkcji rekurencyjnych w Pythonie
Różnice pomiędzy iteracyjnym i rekurencyjnym podejściem do rozwiązywania problemów

Zacznijmy!

Spis treści:

Co to jest rekurencja?

Rekurencja to technika programowania polegająca na wielokrotnym wywoływaniu funkcji w celu rozwiązania problemu.

W swojej istocie rekurencja jest podejściem do rozwiązywania problemów, które polega na podzieleniu złożonego problemu na mniejsze, identyczne podproblemy. Zasadniczo pozwala rozwiązać problem w kategoriach prostszych jego wersji.

Jak więc zaimplementować rekurencję w kodzie? Aby to zrobić, przyjrzyjmy się, jak działają funkcje rekurencyjne.

Zrozumienie funkcji rekurencyjnych

Definiujemy funkcję rekurencyjną, która wywołuje samą siebie w ramach swojej definicji. Każde wywołanie rekurencyjne reprezentuje mniejszą lub prostszą wersję pierwotnego problemu.

Aby mieć pewność, że rekurencja ostatecznie się zakończy, funkcje rekurencyjne muszą zawierać jeden lub więcej przypadków podstawowych — warunków, w których funkcja przestaje się wywoływać i zwraca wynik.

Rozłóżmy to jeszcze bardziej. Funkcja rekurencyjna składa się z:

Przypadek podstawowy: Przypadek podstawowy to warunek (lub warunki), które określają, kiedy rekurencja powinna się zatrzymać. Gdy spełniony jest przypadek podstawowy, funkcja zwraca wynik bez wykonywania dalszych wywołań rekurencyjnych. Przypadek podstawowy jest niezbędny, aby zapobiec nieskończonej rekurencji.
Przypadek rekurencyjny: Przypadek rekurencyjny określa, w jaki sposób podzielić problem na mniejsze podproblemy. W tej części funkcji funkcja wywołuje samą siebie ze zmodyfikowanymi danymi wejściowymi. Każde wywołanie rekurencyjne jest zatem krokiem w kierunku osiągnięcia przypadku podstawowego.

Następnie omówmy, co się dzieje, gdy wywołujesz funkcję rekurencyjną.

Jak rekurencja działa pod maską

Kiedy funkcja jest wywoływana, na stosie wywołań umieszczany jest zapis kontekstu jej wykonania. Rekord ten zawiera informacje o argumentach funkcji, zmiennych lokalnych i lokalizacji, która ma zostać zwrócona po zakończeniu wykonywania funkcji.

W przypadku funkcji rekurencyjnych, gdy funkcja wywołuje samą siebie, nowy rekord jest umieszczany na stosie wywołań, co skutecznie wstrzymuje wykonanie bieżącej funkcji. Stos umożliwia Pythonowi śledzenie wszystkich oczekujących wywołań funkcji, w tym wywołań rekurencyjnych.

Dopóki nie zostanie osiągnięty przypadek podstawowy, rekurencja jest kontynuowana. Kiedy przypadek podstawowy zwraca wynik, wywołania funkcji są rozwiązywane jedno po drugim — przy czym każda funkcja zwraca swój wynik na poprzedni poziom stosu wywołań. Proces ten trwa aż do zakończenia początkowego wywołania funkcji.

Implementacja rekurencji w Pythonie

W tej sekcji omówimy trzy proste przykłady rekurencji:

Obliczanie silni liczby

Obliczanie liczb Fibonacciego

Implementacja wyszukiwania binarnego przy użyciu rekurencji.

Dla każdego przykładu określimy problem, przedstawimy rekurencyjną implementację Pythona, a następnie wyjaśnimy, jak działa rekurencyjna implementacja.

#1. Obliczenia silni przy użyciu rekurencji

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

Obliczenia silni dobrze nadają się do rekurencji, jak pokazano:

Oto funkcja rekurencyjna służąca do obliczenia silni danej liczby 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)

Obliczmy 5! za pomocą funkcji silnia():

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

Zobaczmy teraz jak działa ta funkcja:

Mamy przypadek podstawowy, który sprawdza, czy n jest równe 0 lub 1. Jeśli warunek jest spełniony, funkcje zwracają 1. Przypomnij sobie, że 0! wynosi 1, podobnie jak 1!.
Jeśli n jest większe niż 1, obliczamy n! poprzez pomnożenie n przez silnię n-1. Wyraża się to jako n * silnia (n – 1).
Funkcja wykonuje wywołania rekurencyjne ze zmniejszającymi się wartościami n, aż do osiągnięcia przypadku podstawowego.

#2. Liczby Fibonacciego z rekurencją

Problem: Znajdź termin pod n-tym indeksem w ciąg 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):
	# 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)

Uruchommy funkcję:

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

Oto jak działa ta funkcja:

Zacznijmy od omówienia przypadków podstawowych. Jeśli n wynosi 0, zwraca 0. A jeśli n wynosi 1, zwraca 1. Przypomnijmy, że F(0) = 0 i F(1) = 1.
W przypadku rekurencyjnym, jeśli n jest większe niż 1, funkcja oblicza F(n) poprzez dodanie składników F(n-1) i F(n-2). Jest to wyrażane jako fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
Funkcja wykonuje wywołania rekurencyjne z malejącymi wartościami n, aż dotrze do przypadków podstawowych.

#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):
	# 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)

Funkcja binarySearch dzieli interwał wyszukiwania na pół przy każdym wywołaniu rekurencyjnym, dopóki nie znajdzie celu lub nie ustali, że celu nie ma na liście.

Oto przykładowe uruchomienie 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)
# Output: 4

Rozłóżmy działanie tej funkcji:

W rekurencyjnej implementacji wyszukiwania binarnego mamy dwa przypadki podstawowe. Po pierwsze, jeśli wartość low staje się większa od wartości wysokiej, oznacza to, że elementu docelowego nie ma na liście. Zwracamy więc -1, aby wskazać, że cel nie został znaleziony.
Drugi przypadek podstawowy sprawdza, czy element w środkowym indeksie w połowie bieżącego interwału wyszukiwania jest równy celowi. Jeśli pasują, zwracamy indeks środkowy, wskazując, że znaleźliśmy cel.
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żeli środkowy element jest mniejszy od celu, szukamy prawej połowy wywołując binarySearch(arr, target, mid + 1, high).

Podejście rekursywne a podejście iteracyjne

Podejście iteracyjne — wykorzystujące pętle — to kolejne powszechne podejście do rozwiązywania problemów. Czym więc różni się od rekurencji? Dowiedzmy Się.

Najpierw porównujemy rozwiązania rekurencyjne i iteracyjne wspólnego problemu: obliczania silni liczby.

Oto rekurencyjna implementacja obliczeń silniowych:

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)

Ponieważ wiemy, że silnia liczby nieujemnej jest iloczynem wszystkich liczb od 1 do n, możemy również napisać implementację iteracyjną za pomocą pętli.

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

Obie te implementacje dają identyczne wyniki.

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

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

Ale czy podejście iteracyjne jest preferowane zamiast rekurencji? W przypadku głębokiej rekurencji — ze zbyt dużą liczbą wywołań funkcji — mogą wystąpić błędy z powodu przekroczenia głębokości rekurencji. Pętla jest lepszą opcją w przypadku problemów, których rekurencyjna implementacja wymaga zbyt wielu wywołań funkcji, aby dotrzeć do przypadku podstawowego.

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

CechaPodejście rekurencyjnePodejście iteracyjneStructureWykorzystuje rekurencyjne wywołania funkcji i opiera się na stosie wywołań.Wykorzystuje pętle do iteracji bez dodatkowych wywołań funkcji.Przypadki podstawoweWymagają jawnych przypadków podstawowych, 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 wydajna pamięć i mniej podatna na błędy przepełnienia stosu. Debugowanie Może być trudne do debugowania ze względu na wiele wywołań funkcji i zagnieżdżonych kontekstów wykonywania. Zwykle łatwiejsze do debugowania ze względu na prosty liniowy przepływ wykonywania Podejście .iteracyjne a podejście rekurencyjne

Wniosek

W tym artykule zaczęliśmy od dowiedzenia się, czym jest rekurencja i jak zdefiniować funkcje rekurencyjne za pomocą przypadków podstawowych i relacji rekurencji.

Następnie napisaliśmy trochę kodu w Pythonie — rekurencyjne implementacje typowych problemów programistycznych. Na koniec poznaliśmy różnice między podejściem iteracyjnym i rekurencyjnym oraz zalety i wady każdego z tych podejść.

Następnie przejrzyj listę pytań do rozmowy kwalifikacyjnej w języku Python.