Agnieszka Rybarczyk Homepage
Programowanie w C
Rekurencja
Funkcja wywołuje samą siebie. Oznacza to podział problemu na mniejsze zagnieżdżone podproblemy o identycznej strukturze i rozwiązanie podproblemów przez algorytm nadrzędny.- Bardzo często ułatwia zaprojektowanie rozwiązania, sprawia, że jest ono bardziej czytelne, ale nie zawsze jest optymalna.
- Należy bezwzględnie pamiętać o zaprojektowaniu warunku wyjścia z rekurencji. W przypadku pominięcia tego warunku program zakończy się błędem.
- Trzeba pamiętać, że rekurencja bywa "kosztowna" tzn. im więcej argumentów ma funkcja i im większy jest ich rozmiar, tym mniej rekurencyjnych wywołań jest możliwych.
- W większości zwykłych zastosowań jednak, liczba możliwych zejść rekurencyjnych jest wystarczająco duża. Jeśli program kończy się błędem z tego powodu, bardziej prawdopodobne, że rekurencja jest nieprawidłowo przemyślana/zaprogramowana.
- Używanie rekurencji w programach jest możliwe dzięki podprogramom (procedurom, funkcjom)
- Przykład:
int fi(int liczba) {
if (liczba == 0) // warunek wyjścia z rekurencji
return 1;
else
return 1 + fi(liczba - 1); // wywołanie rekurencyjne
}
- Jeśli rekurencyjna zależność dotyczy więcej niż jednego elementu "wstecz", należy to wziąć pod uwagę w projektowaniu warunku wyjścia z funkcji rekurencyjnej:
int f(int n) {
if (n == 0)
return 1;
else if (n == 1)
return 2;
else
return f(n - 1) * f(n - 2);
}
- Prosty przykład: Napisz rekurencyjną funkcję/procedurę dodającą "1" do zadanej liczby tak długo aż nie będzie równa 10. Porównaj poniższe wersje.
//wersja 1
void rekProc(int& liczba){
if (liczba >= 10) return; //warunek wyjścia z rekurencji
else{
liczba++;
rekProc(liczba);
}
}
//wersja 2
int rekFun(int liczba){
if (liczba >= 10) return liczba; //warunek wyjścia z rekurencji
else{
return rekFun(liczba + 1);
}
}
int main(int argc, _TCHAR* argv[])
{
int liczba1, liczba2;
cin >> liczba1 >> liczba2;
rekProc(liczba2);
cout << " " << rekFun(liczba1) << " " << liczba2 << endl;
system("PAUSE");
return 0;
}
- Bardzo często ułatwia zaprojektowanie rozwiązania, sprawia, że jest ono bardziej czytelne, ale nie zawsze jest optymalna.