path: root / Seminar02 / recursion.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include<iostream>
#include<stack>

int fib(unsigned x) {
    if(x == 0 || x == 1)
        return 1;

    return fib(x - 1) + fib(x - 2);
}

// Малък пример как можем да симулираме рекурсия чрез стек.
int fibStack(unsigned x) {
    std::stack<unsigned> s;
    s.push(x);
    int result = 0;

    while(!s.empty()) {
        int currArg = s.top(); 
        s.pop();

        if(currArg == 1 || currArg == 0)
            ++result;                          // Еквивалентно на return 1;
        else{
            s.push(currArg - 1);            // Еквивалентно на fib(x - 1);
            s.push(currArg - 2);            // Еквивалентно на fib(x - 2);
        }
    }
    return result;
}

int main() {
    std::cout << fib(10) << " " << fibStack(10);
}