Zajímá vás vše o rekurzi v programování? Tento průvodce rekurzí v Pythonu vám pomůže proniknout do této problematiky.
Rekurze je mimořádně užitečná technika při řešení úloh, kterou by měl každý programátor ovládat. Ačkoli se na první pohled může zdát složitá, rekurze vám může pomoci vytvářet elegantnější řešení komplexních problémů.
V tomto tutoriálu se zaměříme na praktické pochopení rekurze pomocí Pythonu. Konkrétně probereme:
- Základní principy rekurze
- Jak fungují rekurzivní funkce
- Implementaci rekurzivních funkcí v Pythonu
- Rozdíly mezi iterativním a rekurzivním přístupem k řešení problémů
Pojďme na to!
Co je to rekurze?
Rekurze je programovací technika, při které funkce volá sama sebe opakovaně, s cílem vyřešit konkrétní problém.
V podstatě se jedná o přístup k řešení problémů, který zahrnuje rozklad složitého problému na menší, identické podproblémy. Umožňuje vám tak řešit problém pomocí jednodušších verzí téhož problému.
Jak tedy rekurzi implementujeme v kódu? Pro pochopení si objasníme, jak fungují rekurzivní funkce.
Jak fungují rekurzivní funkce
Rekurzivní funkce je definována tak, že 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 rekurze nakonec skončila, musí rekurzivní funkce obsahovat jeden nebo více základních případů – to jsou podmínky, při kterých funkce přestane volat sama sebe a vrátí výsledek.
Pojďme si to rozebrat podrobněji. Rekurzivní funkce se skládá z:
- Základní případ: Jedná se o podmínku (nebo podmínky), které určují, kdy se má rekurze zastavit. Když je základní případ splněn, funkce vrátí výsledek, aniž by došlo k dalším rekurzivním voláním. Základní případ je klíčový pro zamezení nekonečné rekurze.
- Rekurzivní případ: Definuje, jak se problém rozdělí na menší podproblémy. V této části funkce se funkce volá sama s upravenými vstupy. Každé rekurzivní volání nás přibližuje k dosažení základního případu.
Podívejme se, co se děje, když zavoláte rekurzivní funkci.
Jak rekurze funguje „pod kapotou“
Když je funkce volána, její kontext provedení se uloží do zásobníku volání. Tento záznam obsahuje informace o argumentech funkce, lokálních proměnných a pozici, kam se má funkce vrátit po svém dokončení.
V případě rekurzivních funkcí, když funkce volá sama sebe, je do zásobníku volání vložen nový záznam, čí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ě rekurzivních volání.
Rekurze pokračuje do té doby, dokud není dosaženo základního případu. Když základní případ vrátí výsledek, volání funkcí se postupně vyhodnocují, přičemž každá funkce vrací 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 si ukážeme tři jednoduché příklady rekurze:
U každého příkladu popíšeme problém, poskytneme rekurzivní implementaci v Pythonu a vysvětlíme, jak rekurzivní implementace funguje.
#1. Výpočet faktoriálu pomocí rekurze
Úkol: Vypočítat faktoriál nezáporného celého čísla n, označovaného jako n!. Matematicky je faktoriál čísla n součinem všech kladných celých čísel od 1 do n.
Výpočet faktoriálu je vhodný pro rekurzivní přístup, jak si ukážeme:
Zde je rekurzivní funkce pro výpočet faktoriálu daného čísla n:
def factorial(n):
# Základní případ
if n == 0 or n == 1:
return 1
# Rekurzivní případ: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Spočítejme 5! pomocí funkce factorial():
factorial_5 = factorial(5) print(factorial(5)) # Výstup: 120
Podívejme se, 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!.
- Pokud je n větší než 1, vypočítáme n! vynásobením n faktoriálem n-1. To se vyjadřuje jako n * faktoriál (n – 1).
- Funkce pokračuje rekurzivními voláními s klesajícími hodnotami n, dokud nedosáhne základního případu.
#2. Fibonacciho čísla s rekurzí
Úkol: Najít člen na n-tém indexu ve Fibonacciho posloupnosti. Fibonacciho posloupnost je definována takto: F(0) = 0, F(1) = 1 a F(n) = F(n-1) + F(n-2) pro n >= 2.
def fibonacciSeq(n):
# Základní případy
if n == 0:
return 0
elif n == 1:
return 1
# Rekurze: 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) # Výstup: 5
Funkce pracuje následovně:
- Nejprve se podívejme na základní případy. Pokud je n rovno 0, vrátí 0. A pokud je n rovno 1, vrátí 1. Připomeňme, že F(0) = 0 a F(1) = 1.
- V rekurzivním případě, pokud je n větší než 1, funkce vypočítá F(n) sečtením členů F(n-1) a F(n-2). To se vyjadřuje jako fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- Funkce pokračuje rekurzivními voláními s klesajícími hodnotami n, dokud nedosáhne základních případů.
#3. Rekurzivní implementace binárního vyhledávání
Úkol: Implementovat algoritmus binárního vyhledávání pomocí rekurze pro 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):
# Základní případ: cílový prvek nenalezen
if low > high:
return -1
mid = (low + high) // 2
# Základní případ: cílový prvek nalezen
if arr[mid] == target:
return mid
# Rekurzivní případ: prohledávání levé nebo pravé části pole
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
Funkce binarySearch dělí interval pro vyhledávání na polovinu s každým rekurzivním voláním, dokud buď nenajde cíl, nebo nezjistí, že cíl v seznamu není.
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) # Výstup: 4
Podívejme se, jak funkce pracuje:
- V rekurzivní implementaci binárního vyhledávání máme dva základní případy. Za prvé, pokud se low stane větší než high, znamená to, že cílový prvek v seznamu není. 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 v rámci aktuálního vyhledávacího intervalu rovná cíli. Pokud se shodují, vrátíme střední index, což znamená, že jsme cíl nalezli.
- 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 v pravé polovině voláním binarySearch(arr, target, mid + 1, high).
Rekurzivní vs. iterativní přístup
Iterativní přístup – používání cyklů – je dalším běžným způsobem, jak řešit problémy. Jak se tedy liší od rekurze? Podívejme se na to.
Nejprve porovnáme rekurzivní a iterativní řešení běžného problému: výpočet faktoriálu čísla.
Zde je rekurzivní implementace výpočtu faktoriálu:
def factorialRec(n):
# Základní případ
if n == 0 or n == 1:
return 1
# Rekurzivní případ: 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 napsat i iterativní implementaci pomocí cyklů.
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) # Výstup: 120 factorial_5 = factorialIter(5) print(factorial_5) # Výstup: 120
Je iterativní přístup preferován před rekurzí? Při hluboké rekurzi – s příliš mnoha voláními funkcí – se můžete setkat s chybami způsobenými překročením hloubky rekurze. Iterace je vhodnější pro problémy, jejichž rekurzivní implementace vyžaduje příliš mnoho volání funkcí pro dosažení základního případu.
Shrňme si rozdíly mezi iterativní a rekurzivní implementací:
| Vlastnost | Rekurzivní přístup | Iterativní přístup |
| Struktura | Využívá rekurzivní volání funkcí a spoléhá se na zásobník volání. | Používá cykly pro iteraci bez dalších volání funkcí. |
| Základní případy | Vyžaduje explicitní základní případy pro zastavení rekurze. | Obvykle používá podmínky pro ukončení cyklu. |
| Výkon | Může být méně paměťově efektivní kvůli zásobníku volání. Hluboká rekurze může občas vést k chybám přetečení zásobníku. | Obecně paměťově efektivnější 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 provedení. | Typicky 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 si vysvětlili, co je to rekurze a jak definovat rekurzivní funkce se základními případy a rekurzivními vztahy.
Následně jsme si ukázali rekurzivní implementace běžných programovacích úloh v Pythonu. Na závěr jsme se naučili o rozdílech mezi iterativním a rekurzivním přístupem a o výhodách a nevýhodách každého z nich.
Podívejte se také na tento seznam otázek pro pohovor v Pythonu.