Úvod do rekurze v Pythonu

Chcete se dozvědět vše o rekurzi v programování? Tento tutoriál o rekurzi v Pythonu vám pomůže začít.

Rekurze je super užitečná technika řešení problémů, kterou můžete přidat do sady nástrojů vašeho programátora. I když je zpočátku často obtížné zabalit si hlavu, rekurze vám může pomoci přijít s elegantnějšími řešeními složitých problémů.

V tomto tutoriálu použijeme přístup k učení rekurze pomocí Pythonu na prvním místě kódu. Konkrétně se budeme zabývat:

Základy rekurze
Rekurzivní funkce a jak fungují
Implementace rekurzivních funkcí v Pythonu
Rozdíly mezi iterativními a rekurzivními přístupy k řešení problémů

Začněme!

Table of Contents

Co je rekurze?

Rekurze je programovací technika, kdy funkce opakovaně volá sama sebe, aby vyřešila problém.

Ve svém jádru je rekurze přístup k řešení problémů, který zahrnuje rozdělení složitého problému na menší, identické dílčí problémy. V podstatě vám umožňuje vyřešit problém z hlediska jednodušších verzí sebe sama.

Jak tedy implementujeme rekurzi v kódu? Abychom tak učinili, pojďme pochopit, jak fungují rekurzivní funkce.

Pochopení rekurzivních funkcí

Definujeme rekurzivní funkci, která v rámci své definice volá sama sebe. Každé rekurzivní volání představuje menší nebo jednodušší verzi původního problému.

Aby bylo zajištěno, že rekurze nakonec skončí, musí rekurzivní funkce obsahovat jeden nebo více základních případů – podmínky, za kterých funkce přestane volat sama sebe a vrátí výsledek.

Pojďme to rozebrat dále. Rekurzivní funkce se skládá z:

Základní případ: Základní případ je podmínka (nebo podmínky), které určují, kdy se má rekurze zastavit. Když je splněn základní případ, funkce vrátí výsledek bez dalších rekurzivních volání. Základní případ je nezbytný, aby se zabránilo nekonečné rekurzi.
Rekurzivní případ: Rekurzivní případ definuje, jak rozdělit problém na menší dílčí problémy. V této části funkce se funkce volá sama s upravenými vstupy. Každé rekurzivní volání je proto krokem k dosažení základního případu.

Dále si proberme, co se stane, když zavoláte rekurzivní funkci.

Jak funguje rekurze pod pokličkou

Když je funkce volána, záznam jejího kontextu provádění je umístěn do zásobníku volání. Tento záznam obsahuje informace o argumentech funkce, lokálních proměnných a umístění, které se má vrátit, jakmile funkce skončí.

V případě rekurzivních funkcí, když funkce volá sama sebe, je nový záznam vložen do zásobníku volání, čímž se účinně pozastaví provádění aktuální funkce. Zásobník umožňuje Pythonu sledovat všechna čekající volání funkcí, včetně těch z rekurzivních volání.

Dokud není dosaženo základního případu, rekurze pokračuje. Když základní případ vrátí výsledek, volání funkcí se vyřeší jedno po druhém – přičemž každá funkce vrátí svůj výsledek na předchozí úroveň zásobníku volání. Tento proces pokračuje, dokud se nedokončí počáteční volání funkce.

Implementace rekurze v Pythonu

V této části prozkoumáme tři jednoduché příklady rekurze:

Výpočet faktoriálu čísla

Počítání Fibonacciho čísel

Implementace binárního vyhledávání pomocí rekurze.

U každého příkladu uvedeme problém, poskytneme rekurzivní implementaci Pythonu a poté vysvětlíme, jak rekurzivní implementace funguje.

#1. Faktorový výpočet pomocí rekurze

Úloha: Vypočítejte faktoriál nezáporného celého čísla n, označeného jako n!. Matematicky je faktoriál čísla n součinem všech kladných celých čísel od 1 do n.

Faktoriální výpočet se dobře hodí k rekurzi, jak je ukázáno:

Zde je rekurzivní funkce pro výpočet faktoriálu daného čísla 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)

Pojďme počítat 5! pomocí funkce factorial():

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

Nyní se podívejme, jak funkce funguje:

Máme základní případ, který kontroluje, zda se n rovná 0 nebo 1. Pokud je podmínka splněna, funkce vrátí 1. Připomeňme, že 0! je 1 a také 1!.
Je-li n větší než 1, vypočítáme n! vynásobením n faktoriálem n-1. To je vyjádřeno jako n * faktoriál (n – 1).
Funkce pokračuje v rekurzivních voláních s klesajícími hodnotami n, dokud nedosáhne základního případu.

#2. Fibonacciho čísla s rekurzí

Problém: Najděte termín na n-tém indexu v Fibonacciho sekvence. Fibonacciho sekvence je definována následovně: F(0) = 0, F(1) = 1 a F(n) = F(n-1) + F(n-2) pro 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)

Spustíme funkci:

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

Funkce funguje takto:

Začněme diskusí o základních případech. Pokud n je 0, vrátí 0. A pokud n je 1, vrátí 1. Připomeňme si F(0) = 0 a F(1) = 1.
V rekurzivním případě, pokud je n větší než 1, funkce vypočítá F(n) přidáním členů F(n-1) a F(n-2). To je vyjádřeno jako fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
Funkce pokračuje v rekurzivních voláních s klesajícími hodnotami n, dokud nedosáhne základních případů.

#3. Rekurzivní implementace binárního vyhledávání

Problém: Implementujte binární vyhledávací algoritmus pomocí rekurze k nalezení pozice cílového prvku v seřazeném seznamu.

Zde je rekurzivní implementace binárního vyhledávání:

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)

Funkce binarySearch dělí interval vyhledávání na polovinu s každým rekurzivním voláním, dokud buď nenajde cíl, nebo nezjistí, že cíl není v seznamu.

Zde je ukázkový běh funkce:

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

Pojďme si rozebrat, co funkce dělá:

V rekurzivní implementaci binárního vyhledávání máme dva základní případy. Za prvé, pokud se nízká stane větší než vysoká, znamená to, že cílový prvek není v seznamu. Takže vrátíme -1, abychom indikovali, že cíl nebyl nalezen.
Druhý základní případ zkontroluje, zda se prvek na středním indexu uprostřed aktuálního intervalu vyhledávání rovná cíli. Pokud se shodují, vrátíme index uprostřed, což znamená, že jsme našli cíl.
V rekurzivním případě, pokud je prostřední prvek větší než cíl, rekurzivně prohledáváme levou polovinu pole voláním binarySearch(arr, target, low, mid – 1). Pokud je prostřední prvek menší než cíl, hledáme pravou polovinu voláním binarySearch(arr, target, mid + 1, high).

Rekurzivní vs. iterativní přístup

Iterativní přístup – používání smyček – je dalším běžným přístupem k řešení problémů. V čem se tedy liší od rekurze? Pojďme to zjistit.

Nejprve porovnáme rekurzivní a iterativní řešení běžného problému: výpočet faktoriálu čísla.

Zde je rekurzivní implementace faktoriálového výpočtu:

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)

Protože víme, že faktoriál nezáporného čísla je součinem všech čísel od 1 do n, můžeme také napsat iterační implementaci pomocí smyček.

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

Obě tyto implementace poskytují stejné výsledky.

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

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

Je ale iterativní přístup preferován před rekurzí? Když dojde k hluboké rekurzi – s příliš mnoha voláními funkcí – můžete narazit na chyby kvůli překročení hloubky rekurze. Opakování je lepší volbou pro problémy, jejichž rekurzivní implementace vyžaduje příliš mnoho volání funkcí k dosažení základního případu.

Pojďme si shrnout rozdíly mezi iterativními a rekurzivními implementacemi:

FeatureRecursive ApproachIterative ApproachStructurePoužívá rekurzivní volání funkcí a spoléhá se na zásobník volání.Používá smyčky pro iteraci bez dalších volání funkcí.Base CasesVyžaduje explicitní základní případy k zastavení rekurze.K ukončení obvykle používá podmínky cyklování.VýkonMůže být méně paměťově efektivní kvůli zásobníku volání . Hluboká rekurze může někdy vést k chybám přetečení zásobníku.Obecně efektivnější paměti a méně náchylné k chybám přetečení zásobníku.Ladění může být náročné kvůli vícenásobným voláním funkcí a vnořeným kontextům provádění.Typické snazší ladění díky přímému lineárnímu průběhu provádění .Iterativní vs rekurzivní přístup

Závěr

V tomto článku jsme se začali učit, co je rekurze a jak definovat rekurzivní funkce se základními případy a rekurzivními vztahy.

Potom jsme napsali nějaký kód Pythonu – rekurzivní implementace běžných programovacích problémů. Nakonec jsme se naučili rozdíly mezi iterativními a rekurzivními přístupy a výhody a nevýhody každého z těchto přístupů.

Dále se podívejte na tento seznam otázek na pohovor v Pythonu.