Pojęcie rekurencji

1.1 Definicja rekurencji i jej główne koncepcje.

Rekurencja to sytuacja, gdy coś robi samo siebie raz za razem. Wyobraź sobie, że masz instrukcję i część tej instrukcji mówi, aby podążać za samą instrukcją. To jakbyś wydał polecenie, aby powtórzyć to samo polecenie.

Przykłady z życia:

Lustra naprzeciw siebie:

Wyobraź sobie, że stoisz między dwoma lustrami. Widzisz swoje odbicie, i w odbiciu też widzisz swoje odbicie, i tak w kółko. To przykład rekurencji, bo każde lustro pokazuje odbicie drugiego lustra.

Matrioszki:

Matrioszka to lalka, w której jest inna lalka, a w tej kolejna, i tak dalej. Kiedy dojdziesz do najmniejszej lalki, nie ma już nic do odkrycia. To jak przypadek bazowy w rekurencji — moment, kiedy należy się zatrzymać.

Dzielnie pizzy:

Wyobraź sobie, że dzielisz pizzę na pół. Następnie bierzesz połowę i znów dzielisz na pół, i tak dalej, aż kawałki staną się zbyt małe, by je dzielić. Dzielnie na kawałki to proces rekurencyjny, a moment, kiedy nie możesz już podzielić kawałka, to przypadek bazowy.

Ważne! Rekurencja to nie nieskończone powtarzanie polecenia, tu chodzi raczej o to, że przy podziale złożonego zadania na części, podejście do rozwiązywania części zadania jest podobne do rozwiązywania całego zadania.

Jak to działa?

Aby zrozumieć rekurencję, trzeba znać dwa podstawowe pojęcia:

• Przypadek bazowy: to warunek, w którym rekurencja się kończy. Na przykład, w przypadku matrioszek przypadek bazowy to kiedy otwierasz najmniejszą matrioszkę i wewnątrz już nic nie ma.
• Przypadek rekurencyjny: to sytuacja, gdy zadanie się powtarza z mniejszymi częściami. W przypadku pizzy dzielisz kawałek, a potem dzielisz połowę i tak dalej.

Dlaczego to jest przydatne?

Rekurencja pomaga rozwiązywać złożone zadania, rozbijając je na prostsze części. Zamiast rozwiązywać całe zadanie naraz, rozwiązujesz je po kawałku.

Inne przykłady z życia:

Bajka w bajce:

Wyobraź sobie, że bohater bajki opowiada inną bajkę, a bohater tamtej bajki zaczyna opowiadać jeszcze inną bajkę. Kiedy jedna z bajek się kończy, wracasz do poprzedniej bajki. Przypadek bazowy to kiedy kończy się ostatnia bajka.

Rekurencyjny rysunek:

Rysujesz duży trójkąt, a następnie w każdym rogu tego trójkąta rysujesz mały trójkąt, i tak dalej, aż trójkąty staną się zbyt małe. Przypadek bazowy to kiedy trójkąt staje się tak mały, że nie można go narysować.

1.2 Przypadek bazowy: definicja i przykłady.

Przypadek bazowy — to warunek, który kończy wywołania rekurencyjne i pozwala funkcji zwrócić określoną wartość. Zazwyczaj to najprostsze i oczywiste rozwiązanie zadania, które nie wymaga dalszej rekurencji.

Przykłady przypadku bazowego:

Silnia liczby:

Silnia liczby n jest oznaczana jako F(n) == 1*2*3*…*n. Tak samo oczywiste, że F(n) == n* F(n-1).

Przypadek bazowy: silnia liczby 0 lub 1 równa się 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Przypadek bazowy
    else:
        return n * factorial(n - 1)
        

Liczby Fibonacciego:

Liczby Fibonacciego to sekwencja: 1, 1, 2, 3, 5, 8, 13, … Gdzie każda następna liczba jest sumą dwóch poprzednich. Dla F(n) == F(n-1) + F(n-2)

Przypadek bazowy: pierwsze dwie liczby Fibonacciego są równe 1, dlatego „zerowa” liczba Fibonacciego równa się 0. Lub F(0) = 0 i F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Przypadek bazowy
    elif n == 1:
        return 1  # Przypadek bazowy
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Przypadek rekurencyjny: definicja i przykłady

Przypadek rekurencyjny — to część funkcji, która rozwiązuje zadanie poprzez wywołanie jej samej z nowymi parametrami, które przybliżają rozwiązanie do przypadku bazowego. Każde wywołanie rekurencyjne zmniejsza lub modyfikuje zadanie, aby ostatecznie osiągnąć przypadek bazowy.

Przykłady przypadku rekurencyjnego:

Silnia liczby:

Przypadek rekurencyjny: silnia liczby n jest równa n pomnożona przez silnię liczby n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Przypadek bazowy
    else:
        return n * factorial(n - 1)  # Przypadek rekurencyjny
        

Liczby Fibonacciego:

Przypadek rekurencyjny: F(n) jest równe sumie F(n-1) i F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Przypadek bazowy
    elif n == 1:
        return 1  # Przypadek bazowy
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Przypadek rekurencyjny
        

1.4 Przykłady rekurencyjnych algorytmów

1. Przechodzenie drzewa binarnego:

Przykład przechodzenia w porządku "in-order".

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Przykład użycia:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Znalezienie maksymalnego elementu na liście:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Przypadek bazowy
    else:
        max_of_rest = find_max(lst[1:])  # Przypadek rekurencyjny
        return max(lst[0], max_of_rest)
        
# Przykład użycia:
print(find_max([1, 5, 3, 9, 2]))  # Wyjście: 9
        
        

3. Rekurencyjne wyszukiwanie binarne:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Przypadek bazowy: element nie znaleziony
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Przypadek bazowy: element znaleziony
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Przypadek rekurencyjny
    else:
        return binary_search(arr, target, left, mid - 1)  # Przypadek rekurencyjny 
# Przykład użycia:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Wyjście: 4