MODUŁ 08
Rekurencja krok po kroku
Rekurencja występuje, gdy funkcja rozwiązuje problem przez wywołanie samej siebie dla mniejszego podproblemu. Każda rekurencja musi mieć:
W skrócie
Rekurencja występuje, gdy funkcja rozwiązuje problem przez wywołanie samej siebie dla mniejszego podproblemu. Każda rekurencja musi mieć:
- warunek bazowy — przypadek, który można rozwiązać bez kolejnego wywołania;
- krok rekurencyjny — przejście do mniejszego problemu;
- postęp — kolejne wywołania zbliżają się do warunku bazowego;
- złożoność — liczbę wywołań i głębokość stosu trzeba uwzględnić.
Rekurencja nie jest automatycznie szybsza ani bardziej elegancka od pętli. Kompilator C++ nie gwarantuje optymalizacji rekurencji ogonowej. Gdy zadanie wymaga rekurencji, ocena tego wymogu powinna być odrębna od testów wyników.
Przykład
Silnia: baza dla 0 i 1, krok mnoży przez mniejszy problem.
long long silnia(int n) {
if (n <= 1) return 1;
return n * silnia(n - 1);
}- Bez bazy rekurencja nie kończy się nigdy.
- Każde wywołanie dostaje ściśle mniejsze
n.
Najpierw bazaNapisz warunek stopu, zanim dopiszesz wywołanie rekurencyjne.