Używamy cookies, żeby zwiększyć Twoje doświadczenia na stronie
Rekursja - Zagnieżdżone jaskinie
Gratulacje, @name! Dotarłeś/aś do ostatniej lekcji Modułu 2!
Wyobraź sobie eksplorację zagnieżdżonych jaskiń w dżungli. Wchodzisz do pierwszej jaskini, znajdujesz przejście do drugiej jaskini, tam znajdujesz przejście do trzeciej... i tak dalej. Aby wrócić, musisz cofać się dokładnie tą samą drogą - wyjść z trzeciej, potem z drugiej, potem z pierwszej.
To jest rekursja - funkcja wywołuje samą siebie, tworząc "zagnieżdżone" wywołania, a potem "cofa się" przez nie wszystkie.
Czym jest rekursja?
Rekursja to technika programowania gdzie funkcja wywołuje samą siebie w swojej definicji.
Kluczowe elementy rekursji:
- Base case (przypadek bazowy) - warunek zatrzymania
- Recursive case (przypadek rekurencyjny) - wywołanie samej siebie
- Progress toward base case - każde wywołanie przybliża do przypadku bazowego
1def countdown(n):
2 """Prosty przykład rekursji"""
3 # Base case - zatrzymaj rekursję
4 if n <= 0:
5 print("Start!")
6 return
7
8 # Recursive case - wywołaj siebie
9 print(n)
10 countdown(n - 1) # Wywołanie z mniejszą wartością (progress!)
11
12countdown(5)
13# Wynik:
14# 5
15# 4
16# 3
17# 2
18# 1
19# Start!Jak działa rekursja - Call Stack
Python używa call stack (stosu wywołań) do zarządzania rekursją:
1def factorial(n):
2 """Silnia: n! = n × (n-1) × (n-2) × ... × 1"""
3 print(f"Wywołuję factorial({n})")
4
5 if n <= 1:
6 print(f"Base case! Zwracam 1")
7 return 1
8
9 result = n * factorial(n - 1) # Rekursja!
10 print(f"Zwracam {n} * factorial({n-1}) = {result}")
11 return result
12
13print(f"\nWynik: {factorial(5)}\n")
14
15# Call stack:
16# factorial(5) → czeka na factorial(4)
17# factorial(4) → czeka na factorial(3)
18# factorial(3) → czeka na factorial(2)
19# factorial(2) → czeka na factorial(1)
20# factorial(1) → zwraca 1 (base case!)
21# factorial(2) → zwraca 2 * 1 = 2
22# factorial(3) → zwraca 3 * 2 = 6
23# factorial(4) → zwraca 4 * 6 = 24
24# factorial(5) → zwraca 5 * 24 = 120Rekursja vs Iteracja
Większość problemów rekurencyjnych można rozwiązać iteracyjnie (pętlami):
1# Rekursja
2def factorial_recursive(n):
3 """O(n) czas, O(n) pamięć (call stack)"""
4 if n <= 1:
5 return 1
6 return n * factorial_recursive(n - 1)
7
8# Iteracja
9def factorial_iterative(n):
10 """O(n) czas, O(1) pamięć"""
11 result = 1
12 for i in range(1, n + 1):
13 result *= i
14 return result
15
16# Obie zwracają to samo
17print(factorial_recursive(5)) # 120
18print(factorial_iterative(5)) # 120Kiedy używać rekursji?
- ✅ Problem ma naturę rekurencyjną (drzewa, grafy, dziel-i-zwyciężaj)
- ✅ Kod staje się prostszy i czytelniejszy
- ✅ Głębokość rekursji jest ograniczona (nie przekroczy limitu stosu)
Kiedy używać iteracji?
- ✅ Problem jest naturalnie iteracyjny
- ✅ Wydajność pamięciowa jest kluczowa
- ✅ Głębokość może być bardzo duża
Klasyczne przykłady rekursji
1. Silnia (Factorial)
1def factorial(n):
2 """
3 n! = n × (n-1)!
4 Base case: 0! = 1, 1! = 1
5 """
6 if n <= 1:
7 return 1
8 return n * factorial(n - 1)
9
10print(factorial(0)) # 1
11print(factorial(1)) # 1
12print(factorial(5)) # 120
13print(factorial(10)) # 36288002. Ciąg Fibonacciego
1def fibonacci(n):
2 """
3 fib(n) = fib(n-1) + fib(n-2)
4 Base cases: fib(0) = 0, fib(1) = 1
5 """
6 if n <= 0:
7 return 0
8 if n == 1:
9 return 1
10 return fibonacci(n - 1) + fibonacci(n - 2)
11
12# Pierwsze 10 liczb Fibonacciego
13for i in range(10):
14 print(f"fib({i}) = {fibonacci(i)}")
15# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34UWAGA: Naiwny Fibonacci to O(2^n) - bardzo wolny! Używaj memoization:
1# Z memoization (zapamiętywanie wyników)
2def fibonacci_memo(n, memo={}):
3 """O(n) z memoization!"""
4 if n in memo:
5 return memo[n]
6
7 if n <= 0:
8 return 0
9 if n == 1:
10 return 1
11
12 memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
13 return memo[n]
14
15# Znacznie szybsze!
16print(fibonacci_memo(50)) # 12586269025 (błyskawicznie!)3. Suma elementów listy
1def sum_list(arr):
2 """
3 Suma listy rekurencyjnie
4 Base case: pusta lista → 0
5 Recursive: pierwszy element + suma reszty
6 """
7 if not arr: # Pusta lista
8 return 0
9 return arr[0] + sum_list(arr[1:])
10
11print(sum_list([1, 2, 3, 4, 5])) # 15
12print(sum_list([])) # 0
13
14# Safari przykład
15discovered_sizes = [1.5, 2.3, 3.1, 1.8, 4.2] # metry
16total_size = sum_list(discovered_sizes)
17print(f"Łączny rozmiar odkrytych gatunków: {total_size}m") # 12.9m4. Odwracanie stringa
1def reverse_string(s):
2 """
3 Odwróć string rekurencyjnie
4 Base case: pusty string lub 1 znak
5 Recursive: ostatni znak + odwrócona reszta
6 """
7 if len(s) <= 1:
8 return s
9 return s[-1] + reverse_string(s[:-1])
10
11print(reverse_string("Python")) # nohtyP
12print(reverse_string("Safari")) # irafaS
13
14# Alternatywna wersja (pierwszy + reszta)
15def reverse_string_v2(s):
16 if len(s) <= 1:
17 return s
18 return reverse_string_v2(s[1:]) + s[0]
19
20print(reverse_string_v2("Darwin")) # niwraD5. Sprawdzanie palindromu
1def is_palindrome(s):
2 """
3 Sprawdź czy string jest palindromem rekurencyjnie
4 Palindrom: czyta się tak samo w obie strony (np. "kajak")
5 """
6 # Usuń spacje i zamień na małe litery
7 s = s.replace(" ", "").lower()
8
9 # Base cases
10 if len(s) <= 1:
11 return True
12
13 # Sprawdź pierwszy i ostatni znak
14 if s[0] != s[-1]:
15 return False
16
17 # Sprawdź środek rekurencyjnie
18 return is_palindrome(s[1:-1])
19
20print(is_palindrome("kajak")) # True
21print(is_palindrome("Python")) # False
22print(is_palindrome("A man a plan a canal Panama")) # True
23print(is_palindrome("level")) # TrueBinary Search - rekurencyjnie
1def binary_search_recursive(arr, target, left=0, right=None):
2 """
3 Wyszukiwanie binarne - O(log n)
4
5 arr: posortowana lista
6 target: szukana wartość
7 left, right: zakres przeszukiwania
8 """
9 if right is None:
10 right = len(arr) - 1
11
12 # Base case - nie znaleziono
13 if left > right:
14 return -1
15
16 # Sprawdź środek
17 mid = (left + right) // 2
18
19 if arr[mid] == target:
20 return mid # Znaleziono!
21 elif arr[mid] < target:
22 # Szukaj w prawej połowie
23 return binary_search_recursive(arr, target, mid + 1, right)
24 else:
25 # Szukaj w lewej połowie
26 return binary_search_recursive(arr, target, left, mid - 1)
27
28# Safari przykład
29species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
30index = binary_search_recursive(species, "Leo")
31print(f"'Leo' na pozycji: {index}") # 2
32
33index = binary_search_recursive(species, "Tyrannosaurus")
34print(f"'Tyrannosaurus' na pozycji: {index}") # -1 (nie znaleziono)Rekursja z wieloma wywołaniami
Suma cyfr liczby
1def sum_digits(n):
2 """
3 Suma cyfr liczby
4 Przykład: 12345 → 1+2+3+4+5 = 15
5 """
6 if n < 10:
7 return n
8 return (n % 10) + sum_digits(n // 10)
9
10print(sum_digits(12345)) # 15
11print(sum_digits(999)) # 27Potęga
1def power(base, exp):
2 """
3 Potęga: base^exp
4 Przykład: power(2, 5) = 32
5 """
6 if exp == 0:
7 return 1
8 if exp == 1:
9 return base
10 return base * power(base, exp - 1)
11
12print(power(2, 5)) # 32
13print(power(3, 4)) # 81
14
15# Optymalizacja - szybsze potęgowanie (dziel i zwyciężaj)
16def power_fast(base, exp):
17 """O(log n) zamiast O(n)!"""
18 if exp == 0:
19 return 1
20 if exp == 1:
21 return base
22
23 # Podziel wykładnik na pół
24 half = power_fast(base, exp // 2)
25
26 if exp % 2 == 0:
27 return half * half # exp parzyste
28 else:
29 return base * half * half # exp nieparzyste
30
31print(power_fast(2, 10)) # 1024 (szybciej!)Rekursja z listami zagnieżdżonymi
1def flatten_list(nested_list):
2 """
3 Spłaszcz zagnieżdżoną listę rekurencyjnie
4 [[1, 2], [3, [4, 5]], 6] → [1, 2, 3, 4, 5, 6]
5 """
6 result = []
7
8 for item in nested_list:
9 if isinstance(item, list):
10 # Rekurencyjnie spłaszcz podlistę
11 result.extend(flatten_list(item))
12 else:
13 result.append(item)
14
15 return result
16
17# Przykład
18nested = [[1, 2], [3, [4, 5]], 6, [7, [8, [9, 10]]]]
19flat = flatten_list(nested)
20print(flat) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
21
22# Safari przykład - zagnieżdżone zespoły
23teams = [
24 ["Darwin", "Alex"],
25 ["Maya", ["Sarah", "Tom"]],
26 "Chen",
27 ["Ahmed", ["Sofia", ["Lisa"]]]
28]
29all_members = flatten_list(teams)
30print(f"Wszyscy członkowie zespołu: {all_members}")Safari przykłady - eksploracja jaskiń
1. Eksploracja zagnieżdżonych jaskiń
1def explore_caves(cave_system, depth=0):
2 """
3 Eksploruj zagnieżdżony system jaskiń
4
5 cave_system: dict z kluczem "name" i opcjonalnie "passages" (lista pod-jaskiń)
6 """
7 indent = " " * depth
8 print(f"{indent}➡️ Wchodzę do: {cave_system['name']}")
9
10 # Base case - jaskinia bez przejść
11 if 'passages' not in cave_system or not cave_system['passages']:
12 print(f"{indent}🏁 Ślepa uliczka! Wracam...")
13 return
14
15 # Recursive case - eksploruj przejścia
16 for passage in cave_system['passages']:
17 explore_caves(passage, depth + 1)
18
19 print(f"{indent}⬅️ Wychodzę z: {cave_system['name']}")
20
21# System jaskiń
22jungle_caves = {
23 "name": "Główna Jaskinia",
24 "passages": [
25 {
26 "name": "Północny tunel",
27 "passages": [
28 {"name": "Komora kryształowa"},
29 {"name": "Wodospad"}
30 ]
31 },
32 {
33 "name": "Wschodni tunel",
34 "passages": [
35 {
36 "name": "Głęboka studnia",
37 "passages": [
38 {"name": "Podziemne jezioro"}
39 ]
40 }
41 ]
42 },
43 {"name": "Zachodni tunel"}
44 ]
45}
46
47explore_caves(jungle_caves)2. Zliczanie odkryć w zagnieżdżonych strukturach
1def count_species(area):
2 """
3 Zlicz gatunki w zagnieżdżonych obszarach
4
5 area: dict z 'species' (lista) i opcjonalnie 'sub_areas' (lista obszarów)
6 """
7 # Zlicz gatunki w tym obszarze
8 count = len(area.get('species', []))
9
10 # Base case - brak podob szarów
11 if 'sub_areas' not in area:
12 return count
13
14 # Recursive case - dodaj z podob szarów
15 for sub_area in area['sub_areas']:
16 count += count_species(sub_area)
17
18 return count
19
20# Obszar ekspedycji
21expedition_area = {
22 "name": "Dżungla Główna",
23 "species": ["Python regius", "Panthera leo"],
24 "sub_areas": [
25 {
26 "name": "Las Północny",
27 "species": ["Gorilla gorilla", "Elephas maximus"],
28 "sub_areas": [
29 {
30 "name": "Rzeka",
31 "species": ["Crocodylus niloticus"]
32 }
33 ]
34 },
35 {
36 "name": "Sawanna",
37 "species": ["Giraffa camelopardalis", "Loxodonta africana", "Panthera leo"]
38 }
39 ]
40}
41
42total = count_species(expedition_area)
43print(f"Łącznie odkryto: {total} gatunki") # 8 gatunków3. Znajdowanie ścieżki w labiryncie
1def find_path_in_maze(maze, row, col, target, path=[]):
2 """
3 Znajdź ścieżkę do celu w labiryncie rekurencyjnie (Backtracking)
4
5 maze: 2D lista ('.' = droga, '#' = ściana, 'T' = cel)
6 row, col: aktualna pozycja
7 target: pozycja celu
8 path: aktualna ścieżka
9 """
10 # Sprawdź czy poza granicami lub ściana
11 if (row < 0 or row >= len(maze) or
12 col < 0 or col >= len(maze[0]) or
13 maze[row][col] == '#' or
14 maze[row][col] == 'V'): # 'V' = visited
15 return False
16
17 # Dodaj do ścieżki
18 path.append((row, col))
19
20 # Base case - znaleziono cel!
21 if (row, col) == target:
22 return True
23
24 # Oznacz jako odwiedzone
25 original = maze[row][col]
26 maze[row][col] = 'V'
27
28 # Spróbuj wszystkich 4 kierunków (góra, dół, lewo, prawo)
29 if (find_path_in_maze(maze, row - 1, col, target, path) or
30 find_path_in_maze(maze, row + 1, col, target, path) or
31 find_path_in_maze(maze, row, col - 1, target, path) or
32 find_path_in_maze(maze, row, col + 1, target, path)):
33 return True
34
35 # Backtrack - usuń z ścieżki i przywróć
36 path.pop()
37 maze[row][col] = original
38 return False
39
40# Przykład labiryntu
41maze = [
42 ['.', '.', '#', '.', '.'],
43 ['.', '#', '.', '#', '.'],
44 ['.', '.', '.', '.', '#'],
45 ['#', '#', '.', '#', '.'],
46 ['.', '.', '.', '.', 'T']
47]
48
49path = []
50start = (0, 0)
51target = (4, 4)
52
53if find_path_in_maze(maze, start[0], start[1], target, path):
54 print(f"Znaleziono ścieżkę! Długość: {len(path)}")
55 print(f"Ścieżka: {path}")
56else:
57 print("Brak ścieżki!")Tail Recursion i optymalizacja
Tail recursion to rekursja gdzie wywołanie rekurencyjne jest ostatnią operacją w funkcji.
1# Nie tail-recursive (mnożenie po wywołaniu)
2def factorial_not_tail(n):
3 if n <= 1:
4 return 1
5 return n * factorial_not_tail(n - 1) # Operacja po wywołaniu!
6
7# Tail-recursive (używa akumulatora)
8def factorial_tail(n, acc=1):
9 if n <= 1:
10 return acc
11 return factorial_tail(n - 1, n * acc) # Wywołanie jest ostatnie!
12
13print(factorial_not_tail(5)) # 120
14print(factorial_tail(5)) # 120UWAGA: Python nie optymalizuje tail recursion automatycznie! Ale możesz przekształcić na iterację.
Rekursja vs Iteracja - wydajność
1import time
2import sys
3
4# Zwiększ limit rekursji (ostrożnie!)
5sys.setrecursionlimit(10000)
6
7def compare_performance(n):
8 """Porównaj wydajność rekursji vs iteracji"""
9
10 # Rekursja
11 start = time.time()
12 def factorial_recursive(x):
13 return 1 if x <= 1 else x * factorial_recursive(x - 1)
14 result_rec = factorial_recursive(n)
15 time_rec = time.time() - start
16
17 # Iteracja
18 start = time.time()
19 def factorial_iterative(x):
20 result = 1
21 for i in range(1, x + 1):
22 result *= i
23 return result
24 result_iter = factorial_iterative(n)
25 time_iter = time.time() - start
26
27 print(f"n = {n}")
28 print(f"Rekursja: {time_rec:.6f}s")
29 print(f"Iteracja: {time_iter:.6f}s")
30 print(f"Iteracja jest {time_rec/time_iter:.1f}x szybsza\n")
31
32compare_performance(100)
33compare_performance(500)
34compare_performance(1000)
35
36# Typowe wyniki:
37# n = 100: Iteracja ~2x szybsza
38# n = 500: Iteracja ~3x szybsza
39# n = 1000: Iteracja ~4x szybsza (i bezpieczniejsza - mniejszy call stack)Zadanie praktyczne
Stwórz "Expedition Analyzer":
- Zlicz wszystkie gatunki w zagnieżdżonej strukturze obszarów
- Znajdź najgłębszy poziom zagnieżdżenia
- Stwórz listę wszystkich nazw obszarów (spłaszcz hierarchię)
- Oblicz średnią liczbę gatunków na obszar
- Znajdź ścieżkę do konkretnego obszaru
Podsumowanie
W tej lekcji nauczyłeś/aś się:
- ✅ Czym jest rekursja (funkcja wywołująca samą siebie)
- ✅ Base case i recursive case
- ✅ Jak działa call stack
- ✅ Rekursja vs iteracja - kiedy używać której
- ✅ Klasycznych przykładów: factorial, Fibonacci, binary search
- ✅ Rekursji z listami zagnieżdżonymi
- ✅ Backtracking (labirynt, ścieżki)
- ✅ Tail recursion i optymalizacji
- ✅ Praktycznych zastosowań Safari
Checkpoint
Przed przejściem dalej:
- [ ] Rozumiesz czym jest rekursja
- [ ] Potrafisz zidentyfikować base case i recursive case
- [ ] Rozumiesz różnicę między rekursją a iteracją
- [ ] Potrafisz napisać prostą funkcję rekurencyjną
- [ ] Rozumiesz pojęcie call stack
- [ ] Wiesz kiedy używać rekursji, a kiedy iteracji
- [ ] Znasz ograniczenia rekursji (stack overflow)
Złota zasada: Rekursja dla problemów naturalnie rekurencyjnych (drzewa, grafy, dziel-i-zwyciężaj), iteracja dla prostych pętli!
🎉 Gratulacje! Ukończyłeś/aś Moduł 2!
W tym module nauczyłeś/aś się:
- ✅ Listy - podstawowa struktura danych
- ✅ Słowniki - pary klucz-wartość
- ✅ Comprehensions - eleganckie tworzenie kolekcji
- ✅ Złożoność algorytmów - Big O notation
- ✅ Sortowanie - różne algorytmy i zastosowania
- ✅ Stosy i kolejki - LIFO i FIFO
- ✅ Rekursja - funkcje wywołujące same siebie
Co dalej? W Module 3 Darwin wprowadzi Cię w Programowanie Obiektowe - jak klasyfikować gatunki używając klas i obiektów! Przygotuj się na naukę OOP, dziedziczenia, enkapsulacji i wiele więcej! 🚀🐍