Kwalifikacja: INF.04 - Projektowanie, programowanie i testowanie aplikacji
Zawód: Technik programista
Który z poniższych problemów jest najczęściej rozwiązywany z zastosowaniem algorytmu rekurencyjnego?
Odpowiedzi
Informacja zwrotna
Generowanie ciągu Fibonacciego to klasyczny przykład problemu, który najczęściej rozwiązuje się za pomocą algorytmu rekurencyjnego. Algorytm rekurencyjny wywołuje sam siebie, dzieląc problem na mniejsze podproblemy, aż do osiągnięcia przypadku bazowego. W przypadku Fibonacciego każda liczba jest sumą dwóch poprzednich, a algorytm rekurencyjny odwzorowuje to wprost poprzez wywołania fib(n-1) + fib(n-2). Rekurencja jest intuicyjna i często stosowana w zadaniach matematycznych, takich jak obliczanie silni czy rozwiązywanie problemów związanych z przeszukiwaniem drzew. Choć rekurencja jest elegancka, dla dużych n może prowadzić do nadmiarowych obliczeń, dlatego często optymalizuje się ją za pomocą pamięci podręcznej (memoizacji) lub iteracyjnych wersji algorytmu.
Obliczanie sumy elementów tablicy jest zadaniem liniowym i najczęściej realizowane za pomocą prostych pętli iteracyjnych, co czyni rekurencję nieefektywnym wyborem dla tego problemu. Wyszukiwanie binarne w posortowanej tablicy można zaimplementować zarówno iteracyjnie, jak i rekurencyjnie, jednak bardziej efektywną metodą jest iteracja, ponieważ rekurencja może prowadzić do większego zużycia pamięci stosu. Sortowanie metodą QuickSort to przykład rekurencyjnego algorytmu, ale nie jest to klasyczny przykład tak intuicyjny jak Fibonacciego – QuickSort rozbija tablicę na mniejsze podzbiory i sortuje je niezależnie, co różni się od prostego obliczania ciągu liczb.