Rekurencja

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Definicja

• Funkcja wywołuje samą siebie
• Prawie wszędzie tam, gdzie używamy pętli
  • pętle można zastąpić rekurencją
• Umożliwia rozwiązywanie pozornie złożonych problemów

Przykład – silnia

$n!$

Przykład – silnia

$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

Przykład – silnia z użyciem rekurencji

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

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

• Wykonuje się w nieskończoność!

Przykład – identyfikacja przypadku bazowego

• Dodaj warunek
  • zapobiega nieskończonemu wykonywaniu algorytmu
• Przypadek bazowy silni -> $n=1$

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

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

Jak działa rekurencja

• Komputer używa stosu do śledzenia funkcji
  • Stos wywołań

Jak działa rekurencja

• factorial(5) startuje
• Zanim factorial(5) się zakończy -> startuje factorial(4)
• Zanim factorial(4) się zakończy -> startuje factorial(3)

Jak działa rekurencja

• factorial(5) startuje
• Zanim factorial(5) się zakończy -> startuje factorial(4)
• Zanim factorial(4) się zakończy -> startuje factorial(3)
• Zanim factorial(3) się zakończy -> startuje factorial(2)

Jak działa rekurencja

• factorial(5) startuje
• Zanim factorial(5) się zakończy -> startuje factorial(4)
• Zanim factorial(4) się zakończy -> startuje factorial(3)
• Zanim factorial(3) się zakończy -> startuje factorial(2)
• Zanim factorial(2) się zakończy -> startuje factorial(1)

Jak działa rekurencja

• factorial(5) startuje
• Zanim factorial(5) się zakończy -> startuje factorial(4)
• Zanim factorial(4) się zakończy -> startuje factorial(3)
• Zanim factorial(3) się zakończy -> startuje factorial(2)
• Zanim factorial(2) się zakończy -> startuje factorial(1)

Jak działa rekurencja

• factorial(1) kończy działanie
  • zwraca 1
• factorial(2) kończy działanie

Jak działa rekurencja

• factorial(1) kończy działanie
  • zwraca 1
• factorial(2) kończy działanie
  • zwraca 2

Jak działa rekurencja

• factorial(1) kończy działanie
  • zwraca 1
• factorial(2) kończy działanie
  • zwraca 2
• factorial(3) kończy działanie
  • zwraca 6

Jak działa rekurencja

• factorial(1) kończy działanie
  • zwraca 1
• factorial(2) kończy działanie
  • zwraca 2
• factorial(3) kończy działanie
  • zwraca 6
• factorial(4) kończy działanie
  • zwraca 24

Jak działa rekurencja

• factorial(1) kończy działanie
  • zwraca 1
• factorial(2) kończy działanie
  • zwraca 2
• factorial(3) kończy działanie
  • zwraca 6
• factorial(4) kończy działanie
  • zwraca 24
• factorial(5) kończy działanie
  • zwraca 120

Jak działa rekurencja

• factorial(1) kończy działanie
  • zwraca 1
• factorial(2) kończy działanie
  • zwraca 2
• factorial(3) kończy działanie
  • zwraca 6
• factorial(4) kończy działanie
  • zwraca 24
• factorial(5) kończy działanie
  • zwraca 120

Programowanie dynamiczne

• Technika optymalizacji
• Głównie stosowana w rekurencji
• Może zmniejszyć złożoność algorytmów rekurencyjnych
• Stosowana, gdy:
  • Problem można podzielić na mniejsze podproblemy
  • Podproblemy nakładają się na siebie
• Rozwiązania podproblemów są zapisywane, co eliminuje potrzebę ponownych obliczeń
  • Memoizacja

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie