Embercode: AI-powered software engineer course

1. What does this program print? ``

cpp
#include <iostream>
long long calls = 0;
long long fib(int n) {
    ++calls;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}
int main() {
    std::cout << fib(5) << " " << calls << "\n";
}

``

8 155 155 95 25

2. What does this program print? ``

cpp
#include <iostream>
long long calls = 0;
long long ways(int n) {
    ++calls;
    if (n == 0) return 1;
    if (n < 0) return 0;
    return ways(n - 1) + ways(n - 2) + ways(n - 3);
}
int main() {
    long long a = ways(3);
    std::cout << "ways(3) = " << a << ", calls = " << calls << "\n";
}

``

ways(3) = 3, calls = 13ways(3) = 4, calls = 7ways(3) = 4, calls = 25ways(3) = 4, calls = 13

3. What does this program print? ``

cpp
#include <iostream>
#include <map>
std::map<int, long long> memo;
long long calls = 0;
long long fib(int n) {
    ++calls;
    if (n < 2) return n;
    if (auto found = memo.find(n); found != memo.end()) return found->second;
    long long answer = fib(n - 1) + fib(n - 2);
    memo[n] = answer;
    return answer;
}
int main() {
    long long a = fib(10);
    std::cout << a << " calls=" << calls << " entries=" << memo.size() << "\n";
}

``

55 calls=19 entries=955 calls=11 entries=955 calls=19 entries=1055 calls=177 entries=9

4. How many calls does naive Fibonacci make for input n, according to the recursion trees lesson?

n, one call per stepfib(n) squared2 * fib(n + 1) - 12 to the power of n

5. After the memo is added, how does the number of calls for memoised fib(n) grow as n goes up?

It grows in a straight line: 2 * n - 1 callsIt grows about 1.6 times for each step up in nIt grows as fib(n), one call per answerIt grows as n * n, one call per pair

Trees and memo