Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

Rekurzija

Rekurzija znači da funkcija poziva samu sebe, izravno ili putem drugih funkcija. Da bi se izračun završio, potreban je dohvatljiv osnovni slučaj i rekurzivni koraci koji napreduju prema njemu.

Verzija: C++23; repository compiler flag, production runtime not attested

Sintaksa

ReturnType function(Parameters) {
    if (base_condition) return base_value;
    return combine(function(smaller_arguments));
}

Rekurzija (recursion) je tehnika u kojoj funkcija poziva samu sebe izravno ili neizravno putem drugih funkcija. Ne zahtijeva posebnu ključnu riječ: koristi uobičajenu sintaksu poziva funkcije. C++ dopušta rekurzivne pozive, ali main se ne smije pozivati rekurzivno.

Tipičan algoritam ima osnovni slučaj, koji vraća rezultat bez dodatnog poziva, i rekurzivni korak, koji smanjuje problem. Za ulazne podatke za koje bi se izračun trebao završiti, svaki niz poziva mora dosegnuti osnovni slučaj. Sam uvjet zaustavljanja nije dovoljan ako ga argumenti nikad ne ispune.

U primjeru sum_to(5) izračunava zbroj od 1 do 5, uključujući obje granice. Pozivi smanjuju n dok ne dosegne 0; pri uzastopnim povratcima zatim se zbrajaju vrijednosti na čekanju i dobiva se 15. Svaki poziv ima vlastiti parametar n; nije riječ o jednoj zajedničkoj varijabli. Za n <= 0 funkcija vraća 0.

Nemoj smatrati primjer rješenjem za proizvoljno velike ulazne podatke: duboka rekurzija može iscrpiti izvršne resurse, a zbroj izvan raspona tipa int uzrokuje nedefinirano ponašanje. Za velike ulazne podatke razmotri petlju i provjere raspona. Navedeni izvor razvojni je nacrt standarda, a ne nepromjenjiva publikacija C++23; primjer koristi sintaksu kompatibilnu s C++23.

Primjeri

#include <iostream>

int sum_to(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(5) << '\n';
}

Rezultat

15

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori