Studia informatyka – rekurencja

Rekurencja

Technika programowania, w której funkcja wywołuje samą siebie w celu rozwiązania problemu.

Podstawowy przypadek

Stan, w którym rekurencyjne wywołanie się kończy, aby uniknąć nieskończonej pętli.

Zastosowanie rekurencji

Stosowana do rozwiązywania problemów takich jak obliczanie silni, ciągi Fibonacciego, przeszukiwanie drzew.

Prawda czy fałsz: Rekurencja jest zawsze bardziej efektywna niż iteracja.

Fałsz, ponieważ rekurencja może prowadzić do większego zużycia pamięci i czasu.

Przykład problemu rekurencyjnego

Obliczanie n-tej liczby Fibonacciego za pomocą funkcji rekurencyjnej.

Drewno rekurencyjne

Struktura danych, w której każdy węzeł reprezentuje wywołanie rekurencyjne.

Złożoność czasowa rekurencji

Analizowana na podstawie liczby wywołań i warunków końcowych.

Rekurencja a iteracja

Rekurencja stosuje wywołania funkcji, podczas gdy iteracja wykorzystuje pętle do powtarzania działań.

Rekurencyjna definicja!

Definicja, która odnosi się do samej siebie, np. lista zdefiniowana jako element i lista mniejszych elementów.

Wnioski z rekurencji

Rekurencja upraszcza złożone problemy, ale wymaga ostrożności w projektowaniu.

Przykład: silnia

Silnia n! zdefiniowana jako $\displaystyle n! = n \cdot (n-1)!$ z podstawowym przypadkiem $\displaystyle 0! = 1$.

Ciąg Fibonacciego

Zdefiniowany rekurencyjnie jako $\displaystyle F(n) = F(n-1) + F(n-2)$ z podstawowymi przypadkami $\displaystyle F(0) = 0$, $\displaystyle F(1) = 1$.

Algorytm QuickSort

Algorytm sortowania oparty na rekurencji, dzieli tablicę na mniejsze części i sortuje je.

Rekurencyjne przeszukiwanie binarne

Szybki algorytm wyszukiwania w posortowanej tablicy, dzielący tablicę na pół.

Prawda czy fałsz: Rekurencja zawsze prowadzi do lepszego kodu.

Fałsz, chociaż rekurencyjny kod jest często bardziej elegancki, może być mniej efektywny.

Problem wież Hanoi

Klasyczny problem rekurencyjny, gdzie celem jest przeniesienie wież z jednego miejsca na drugie.

Różnica między rekurencją a rekurencją ogonową

Rekurencja ogonowa zwraca wynik bez dalszych obliczeń po wywołaniu, eliminując potrzeby stosu.

Zastosowania rekurencji

Rozwiązywanie problemów związanych z obliczeniami, strukturami danych, algorytmami grafowymi.

Grafy i rekurencja

Rekurencja jest używana do przeszukiwania grafów, np. w algorytmie DFS (Depth-First Search).

Rekurencja vs. pamięć

Rekurencyjne wywołania mogą zużywać więcej pamięci przez stos wywołań, co może prowadzić do błędów przepełnienia stosu.

Złożoność rekurencyjna

Można analizować za pomocą równań rekurencyjnych, np. $\displaystyle T(n) = T(n-1) + O(1)$ dla silni.

Obsługa błędów w rekurencji

Ważne jest, aby zapewnić poprawne warunki końcowe, aby uniknąć nieskończonych wywołań.