Agnieszka Rybarczyk Homepage

• Home
• Publications
• Conferences & Seminars
• Honors
• For Students

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;
    }