Algorytm rekurencyjny to taki, w którym rozwiązanie problemu jest zdefiniowane przez odwołanie do tego samego problemu dla mniejszego przypadku. W kodzie źródłowym najczęściej widać to jako sytuację, gdy funkcja/procedura wywołuje samą siebie (bezpośrednio) albo prowadzi do własnego wywołania pośrednio. Kluczowym elementem poprawnej rekurencji jest przypadek bazowy, czyli warunek, w którym dalsze wywołania nie następują i można zwrócić wynik.
Odpowiedź "rekurencyjny." jest poprawna, gdy przedstawiony program zawiera samowywołanie oraz warunek stopu. To odróżnia rekurencję od zwykłego powtarzania instrukcji.
Dlaczego pozostałe odpowiedzi nie pasują:
- "iteracyjny." – iteracja polega na powtarzaniu bloku instrukcji przy użyciu pętli (np. for, while) i zwykle nie wymaga stosu wywołań funkcji. Program może wykonywać podobne kroki, ale jeśli robi to poprzez samowywołania funkcji, to jest to rekurencja, nie iteracja.
- "sortujący." – to określenie celu algorytmu (sortowanie danych). Rekurencja/iteracja opisuje technikę realizacji. Wiele algorytmów sortowania może być rekurencyjnych, ale samo słowo "sortujący" nie wynika wyłącznie ze struktury wywołań; trzeba by jeszcze rozpoznać, że program porządkuje elementy według klucza.
- "podstawieniowy." – nie jest to standardowa, powszechnie nauczana kategoria algorytmu w tym kontekście. W zadaniach egzaminacyjnych częściej klasyfikuje się algorytmy jako rekurencyjne, iteracyjne, zachłanne, dynamiczne, dziel-i-zwyciężaj itp.
Wskazówka egzaminacyjna: aby pewnie rozpoznać rekurencję, szukaj (1) samowywołania funkcji oraz (2) warunku, który zatrzymuje dalsze wywołania. Brak warunku stopu oznacza ryzyko nieskończonej rekurencji i w praktyce błąd wykonania (np. przepełnienie stosu).
