Pytanie 1
Funkcja f(n) = nf(n-1) dla n>1 w przeciwnym wypadku f(n) = 1 jest przykładem
A. obliczania wyrazu ciągu Fibonacciego.
B. rekurencji.
C. iteracji.
D. obliczania n–tej potęgi liczby n.
Funkcja f(n) = n*f(n-1) dla n>1 i f(n) = 1 w przeciwnym wypadku jest klasycznym przykładem rekurencji. W informatyce, rekurencja oznacza, że dana funkcja wywołuje samą siebie, aż do uzyskania tzw. warunku bazowego (czyli sytuacji, kiedy przestaje się wywoływać rekurencyjnie). Dokładnie tak jest w tym przypadku – dla n równego 1 lub niższego, funkcja zwraca 1 i nie wywołuje się dalej, a dla n większego od 1, każdorazowo wywołuje się z argumentem mniejszym o 1. Typowym przykładem tego typu funkcji jest silnia, czyli operacja matematyczna wykorzystywana m.in. w kombinatoryce, kryptografii czy analizie algorytmów. Takie podejście, choć bardzo eleganckie i naturalne w wielu zastosowaniach matematycznych, w praktyce programistycznej wymaga ostrożności – nieumiejętne stosowanie rekurencji może prowadzić do przepełnienia stosu (stack overflow). Optymalnie, przy dużych danych warto sięgnąć po podejście iteracyjne lub tzw. rekurencję ogonową, która bywa lepiej wspierana przez niektóre kompilatory. Moim zdaniem, umiejętność rozpoznania i zrozumienia rekurencji jest jedną z kluczowych kompetencji każdego programisty – czy to w Pythonie, Javie, czy C++. Warto też zauważyć, że rekurencja, chociaż czasem wydaje się mniej wydajna, pozwala bardzo klarownie zapisać nawet złożone problemy, na przykład przy przeszukiwaniu struktur drzewiastych czy rozwiązywaniu łamigłówek typu wieże Hanoi.
