Jaką istotną właściwość ma algorytm rekurencyjny?
Kluczową cechą algorytmu rekurencyjnego jest to, że zawiera on wywołanie samego siebie. Rekurencja pozwala na eleganckie i zwięzłe rozwiązanie problemów, które można podzielić na mniejsze, powtarzające się podproblemy. Każde wywołanie rekurencyjne zmniejsza złożoność problemu, aż do osiągnięcia przypadku bazowego, który kończy dalsze wywołania i rozpoczyna proces zwracania wyników w górę stosu wywołań. Rekurencja znajduje zastosowanie w algorytmach takich jak DFS (przeszukiwanie w głąb), sortowanie szybkie (QuickSort) oraz algorytmy obliczające wartości liczb Fibonacciego i silni.
Wywołanie funkcji wielokrotnie w jednej iteracji jest charakterystyczne dla algorytmów iteracyjnych, a nie rekurencyjnych. Podział algorytmu na wiele niezależnych funkcji to część modularności i nie wskazuje jednoznacznie na rekurencję. Algorytmy działające wyłącznie na tablicach dynamicznych mogą być zarówno iteracyjne, jak i rekurencyjne, jednak to rekurencyjne wywołanie samego siebie stanowi kluczowy wyróżnik rekurencyjnego podejścia do problemów.