Algoritmi → Rekurzija i bektreking → Faktorijel, stepen i NZD – rekurzivno

Faktorijel, stepen i NZD – rekurzivno

Faktorijel

Faktorijel je proizvod prvih n prirodnih brojeva: n! = 1 · 2 · … · n, a po dogovoru 0! = 1. Rekurzivna definicija sledi direktno: n! = n · (n − 1)!.

#include <iostream>
using namespace std;

long long faktorijel(int n) {
    if (n <= 1) return 1;                 // 0! = 1! = 1
    return n * faktorijel(n - 1);
}

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

Faktorijel raste vrlo brzo: 20! je oko 2,4·10¹⁸ i to je najveći faktorijel koji staje u long long. Za veće n u zadacima se obično traži ostatak pri deljenju (npr. sa 10⁹+7) – vidi lekciju Kombinatorika.

Stepen broja: sporo i brzo

Najjednostavnija definicija je xn = x · xn−1. Ona pravi n poziva. Mnogo brže je koristiti polovljenje izložioca:

• ako je n parno: xn = (xn/2)2;
• ako je n neparno: xn = x · xn−1.

Tako se izložilac bar na svaka dva koraka prepolovi, pa je broj poziva oko 2·log₂ n – za n = 1018 to je oko 120 poziva umesto 10¹⁸.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

// x^n po modulu MOD, za n do 10^18
long long stepen(long long x, long long n) {
    if (n == 0) return 1;                     // x^0 = 1
    long long pola = stepen(x, n / 2);        // jedan poziv za n/2 – ne dva!
    long long rez = pola * pola % MOD;
    if (n % 2 == 1) rez = rez * (x % MOD) % MOD;
    return rez;
}

int main() {
    long long x, n;
    cin >> x >> n;
    cout << stepen(x, n) << endl;
    return 0;
}

Važno: rezultat poziva za n / 2 sačuvaj u promenljivoj. Napisano kao stepen(x, n/2) * stepen(x, n/2), rešenje bi opet pravilo oko n poziva. Ista ideja bez rekurzije objašnjena je u lekciji Algoritam brzog stepenovanja.

Euklidov algoritam (NZD)

Najveći zajednički delilac zadovoljava nzd(a, b) = nzd(b, a mod b), a nzd(a, 0) = a. To je skoro doslovno rekurzivna funkcija:

#include <iostream>
using namespace std;

long long nzd(long long a, long long b) {
    if (b == 0) return a;
    return nzd(b, a % b);
}

int main() {
    long long a, b;
    cin >> a >> b;
    long long d = nzd(a, b);
    cout << "NZD = " << d << ", NZS = " << a / d * b << endl;   // prvo deli, pa množi
    return 0;
}

Broj koraka je mali (logaritamski), pa ovde nema opasnosti od duboke rekurzije. Više o NZD i NZS: Određivanje NZD i NZS.

Fibonačijev niz: kada rekurzija postane spora

Fibonačijev niz: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2). Direktna rekurzija je tačna, ali svaki poziv pravi dva nova, pa se isti brojevi računaju mnogo puta:

#include <iostream>
using namespace std;

long long pozivi = 0;

long long fib(int n) {
    pozivi++;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);       // dva poziva -> eksponencijalno mnogo poziva
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << " (poziva: " << pozivi << ")" << endl;
    return 0;
}

Za n = 30 to je preko 2,6 miliona poziva, a za n = 50 program bi radio minutima. Rešenje je da se jednom izračunate vrednosti zapamte (memoizacija) – to je početak dinamičkog programiranja: Fibonačijev niz, memoizacija i DP.

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