Co to jest rekurencja?

Rekurencja to technika stosowana w programowaniu i matematyce, polegająca na tym, że funkcja lub algorytm wywołuje sam siebie, aby rozwiązać problem. Zadanie dzieli się na mniejsze podzadania, które są rozwiązywane poprzez kolejne wywołania tej samej funkcji, aż do osiągnięcia tzw. przypadku bazowego — czyli stanu, w którym dalsze wywoływanie rekurencyjne nie jest już potrzebne.

Przykładem rekurencji może być obliczanie silni liczby. Silnia liczby n (oznaczana jako n!) to iloczyn wszystkich liczb naturalnych od 1 do n. Można ją zdefiniować rekurencyjnie w następujący sposób:

• Dla n = 0, wartość silni wynosi 1 (przypadek bazowy).
• Dla n > 0, n! = n * (n-1)!, czyli silnia liczby n to n pomnożone przez silnię liczby n-1.

Na przykład:

5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1

Funkcje rekurencyjne są użyteczne w wielu algorytmach, np. w sortowaniu, przeszukiwaniu drzew czy rozwiązywaniu problemów takich jak Wieże Hanoi. Jednak nadużywanie rekurencji może prowadzić do nadmiernego zużycia pamięci (tzw. stosu) i wydłużenia czasu wykonywania programów, dlatego ważne jest, aby dobrze zrozumieć, kiedy i jak z niej korzystać.

Prostszym przykładem rekurencji może być obliczanie sumy liczb od 1 do n. Rekurencyjna funkcja dodaje n do sumy liczb od 1 do n-1, aż osiągnie przypadek bazowy, czyli n równe 1.

def suma(n):

    if n == 1:  # przypadek bazowy

        return 1

    else:

        return n + suma(n-1)  # wywołanie rekurencyjne

Rekurencja w tym przypadku sprowadza problem (obliczenie sumy) do coraz prostszych kroków, aż dochodzimy do najprostszego przypadku, który nie wymaga dalszego wywoływania funkcji.

to jak można napisać algorytm dodawania liczb od 1 do 5 przy użyciu rekurencji, ale w formie, którą można łatwo zaimplementować w Excelu. Ponieważ Excel nie obsługuje rekurencji w formie, jak w programowaniu, użyjemy formuł krokowych, które rozbijają problem na mniejsze części.

Instrukcje:

1. Wprowadź liczby od 1 do 5 do osobnych komórek:

   • W komórkach A1 do A5 wpisz liczby 1, 2, 3, 4, 5.

2. Utwórz kolumnę sum częściowych:

• W komórce B1 wprowadź formułę dla pierwszej liczby:

=A1

W komórce B2 wprowadź formułę, która dodaje wartość w komórce B1 (czyli sumę liczb do poprzedniej liczby) do wartości w komórce A2:

=B1 + A2

1. • Skopiuj tę formułę w dół do komórek B3, B4 i B5.

2. Wynik:

   • W komórce B5 otrzymasz sumę liczb od 1 do 5, która wynosi 15.

Objaśnienie:

• W kolumnie A masz liczby, które chcesz dodać.
• W kolumnie B tworzysz sumę krok po kroku, dodając każdą kolejną liczbę do sumy poprzednich.
• Excel nie używa rekurencji w klasycznym sensie, ale poprzez kolejne sumowanie uzyskujesz efekt podobny do rekurencji.

Efekt końcowy:

A (Liczby)	B (Sumy)
1	1
2	3
3	6
4	10
5	15

Kolumna B pokazuje, jak sumy rosną krok po kroku, aż do ostatecznego wyniku 15 w komórce B5.