Porozumění rekurzi

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Definice

• Funkce volající samu sebe
• Téměř všude, kde používáme smyčky
  • lze smyčky nahradit rekurzí
• Umožňuje řešit zdánlivě složité problémy

Příklad – faktoriál

$n!$

Příklad – faktoriál

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120

Příklad – faktoriál pomocí rekurze

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

• Běží donekonečna!

Příklad – identifikace základního případu

• Přidejte podmínku
  • zajistí, že algoritmus neběží donekonečna
• Základní případ faktoriálu -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

Jak rekurze funguje

• Počítač používá zásobník ke sledování funkcí
  • Zásobník volání

Jak rekurze funguje

• factorial(5) začíná
• Než skončí factorial(5) -> začíná factorial(4)
• Než skončí factorial(4) -> začíná factorial(3)

Jak rekurze funguje

• factorial(5) začíná
• Než skončí factorial(5) -> začíná factorial(4)
• Než skončí factorial(4) -> začíná factorial(3)
• Než skončí factorial(3) -> začíná factorial(2)

Jak rekurze funguje

• factorial(5) začíná
• Než skončí factorial(5) -> začíná factorial(4)
• Než skončí factorial(4) -> začíná factorial(3)
• Než skončí factorial(3) -> začíná factorial(2)
• Než skončí factorial(2) -> začíná factorial(1)

Jak rekurze funguje

• factorial(5) začíná
• Než skončí factorial(5) -> začíná factorial(4)
• Než skončí factorial(4) -> začíná factorial(3)
• Než skončí factorial(3) -> začíná factorial(2)
• Než skončí factorial(2) -> začíná factorial(1)

Jak rekurze funguje

• factorial(1) končí
  • vrací 1
• factorial(2) končí

Jak rekurze funguje

• factorial(1) končí
  • vrací 1
• factorial(2) končí
  • vrací 2

Jak rekurze funguje

• factorial(1) končí
  • vrací 1
• factorial(2) končí
  • vrací 2
• factorial(3) končí
  • vrací 6

Jak rekurze funguje

• factorial(1) končí
  • vrací 1
• factorial(2) končí
  • vrací 2
• factorial(3) končí
  • vrací 6
• factorial(4) končí
  • vrací 24

Jak rekurze funguje

• factorial(1) končí
  • vrací 1
• factorial(2) končí
  • vrací 2
• factorial(3) končí
  • vrací 6
• factorial(4) končí
  • vrací 24
• factorial(5) končí
  • vrací 120

Jak rekurze funguje

• factorial(1) končí
  • vrací 1
• factorial(2) končí
  • vrací 2
• factorial(3) končí
  • vrací 6
• factorial(4) končí
  • vrací 24
• factorial(5) končí
  • vrací 120

Dynamické programování

• Optimalizační technika
• Primárně aplikována na rekurzi
• Může snížit složitost rekurzivních algoritmů
• Použití:
  • Problémy dělitelné na menší podproblémy
  • Podproblémy se překrývají
• Řešení podproblémů jsou uložena, čímž se zabrání opakovaným výpočtům
  • Memoizace

Lass uns üben!

Datové struktury a algoritmy v Pythonu