Algoritmi → Rekurzija i bektreking → Uvod u rekurziju

Uvod u rekurziju

Šta je rekurzija?

Zamisli red ljudi i pitanje „koji si po redu?“. Osoba ne broji ceo red, nego pita osobu ispred sebe i svom odgovoru doda 1. Prva osoba u redu ne pita nikoga – ona zna da je prva. Tako radi i rekurzivna funkcija:

• bazni slučaj – najmanji problem, čiji je odgovor poznat bez novih poziva (prva osoba u redu);
• rekurzivni korak – problem se svodi na isti, ali manji problem (pitaj osobu ispred sebe i dodaj 1).

Bez baznog slučaja funkcija bi se pozivala beskonačno – program se prekida greškom (prekoračenje steka).

Prvi primer: odbrojavanje

Funkcija ispisuje broj n, a zatim „ostatak posla“ prepušta pozivu za n - 1:

#include <iostream>
using namespace std;

void odbrojavanje(int n) {
    if (n == 0) {                 // bazni slučaj
        cout << "Start!" << endl;
        return;
    }
    cout << n << " ";
    odbrojavanje(n - 1);          // rekurzivni korak: isti posao za manji broj
}

int main() {
    odbrojavanje(5);
    return 0;
}

Izlaz: 5 4 3 2 1 Start!. Svaki poziv radi samo mali deo posla – ispisuje jedan broj.

Kako se izvršava: stek poziva

Funkcija koja vraća vrednost čeka rezultat poziva za manji problem, pa tek onda završava svoj račun. Pogledajmo zbir prvih n prirodnih brojeva: zbir(n) = n + zbir(n - 1), a zbir(0) = 0.

#include <iostream>
using namespace std;

int zbir(int n) {
    if (n == 0) return 0;         // bazni slučaj
    return n + zbir(n - 1);       // čeka rezultat za n - 1
}

int main() {
    int n;
    cin >> n;
    cout << zbir(n) << endl;
    return 0;
}

Nedovršeni pozivi čuvaju se na steku poziva: poslednji započet poziv prvi se završava. Zato je dubina rekurzije ograničena – za nekoliko stotina hiljada ugnježdenih poziva memorija za stek može da se potroši.

Rad pre i posle rekurzivnog poziva

Redosled naredbi u odnosu na rekurzivni poziv menja rezultat. Funkcija ispod ispisuje cifre broja s leva na desno, iako se cifre izdvajaju s desna (n % 10): ispis je posle poziva, pa se izvršava tek kada se vrate svi kraći pozivi.

#include <iostream>
using namespace std;

void cifre(int n) {
    if (n < 10) {                 // jednocifren broj: bazni slučaj
        cout << n << " ";
        return;
    }
    cifre(n / 10);                // prvo sve cifre osim poslednje
    cout << n % 10 << " ";        // pa poslednja cifra
}

int main() {
    int n;
    cin >> n;
    cifre(n);
    cout << endl;
    return 0;
}

Ako se ispis premesti pre poziva (cout << n % 10; cifre(n / 10);), cifre se ispisuju obrnutim redom.

Rekurzija ili petlja?

Svaka rekurzija može da se zameni petljom (ponekad uz sopstveni stek), ali je rekurzivno rešenje često mnogo kraće i jasnije – videćemo to kod Hanojskih kula i bektrekinga.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje