Który z poniższych problemów jest najczęściej rozwiązywany z zastosowaniem algorytmu rekurencyjnego?

Wyjaśnienie

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.