Pytanie 1
Który fragment kodu ilustruje zastosowanie rekurencji?
Blok 1:int fn(int a) { if(a==1) return 1; return fn(a-1)+2; } | Blok 2:int fn(int a) { if(a==1) return 1; return (a-1)+2; } |
Blok 3:int fn(int a) { if(a==1) return 1; return fun(a-1)+2; } | Blok 4:int fn(int a) { if(a==1) return 1; return 2; } |
A. Blok 3
B. Blok 1
C. Blok 4
D. Blok 2
Wiele osób myli pojęcie rekurencji z prostym przetwarzaniem argumentów funkcji albo próbą wywołania innej funkcji. W przypadku Bloku 2 mamy tylko zwykłe odejmowanie i dodawanie – funkcja fn nie wywołuje samej siebie, więc nie występuje tu rekurencja. To jest bardzo częsty błąd, gdzie ktoś widzi podobieństwo w nazwach i strukturze, ale nie dostrzega istoty rekurencji, czyli tego samowywołania z innym argumentem. Blok 3 z kolei próbuje wywołać inną funkcję (fun zamiast fn), więc to również nie jest rekurencja, tylko – w najlepszym wypadku – jakaś forma współdziałania funkcji, ale nie spełnia definicji rekurencji. Częsty błąd to mylenie rekurencji z przekazywaniem sterowania do innych funkcji. Natomiast Blok 4 jest już najprostszym przypadkiem – nie wywołuje żadnej funkcji w środku, po prostu zawsze zwraca 2, poza przypadkiem bazowym. Brak tu jakiejkolwiek logiki rekurencyjnej. W praktyce programistycznej rekurencja to bardzo specyficzny wzorzec, gdzie kluczowe jest istnienie sprawdzalnego warunku zakończenia (tzw. przypadek bazowy) oraz wywołanie tej samej funkcji, ale z „mniejszym” lub „prostszym” przypadkiem. Bez tych elementów nie można mówić o poprawnej implementacji rekurencji. Osobiście zauważyłem, że wielu uczniów próbuje używać rekurencji do wszystkiego, nie rozumiejąc, że bez samowywołania i przypadku bazowego to po prostu nie działa tak, jak powinno. Branżowe standardy jasno wskazują, że rekurencja jest narzędziem do rozwiązywania problemów, które mają naturalną strukturę rekurencyjną – na przykład przetwarzanie struktur drzewiastych, rozwiązywanie łamigłówek typu wieże Hanoi, czy sortowanie szybkie (quick sort). Jeśli jednak funkcja nie wywołuje samej siebie, nie spełnia warunków rekurencji, nawet jeśli operuje na podobnych argumentach lub odwołuje się do innych funkcji.
