C++ Recursion

In recursion a function calls itself to solve a smaller copy of the problem. Every recursion needs a base case (where it stops) and a recursive case.

#include <iostream>

unsigned long long factorial(int n) {
    if (n <= 1) return 1;                // base case
    return n * factorial(n - 1);         // recursive case
}

int main() {
    std::cout << factorial(5) << '\n';
    std::cout << factorial(10) << '\n';
    std::cout << factorial(20) << '\n';
}

Fibonacci and memoization

#include <iostream>
#include <unordered_map>

unsigned long long fib(int n, std::unordered_map<int, unsigned long long>& cache) {
    if (n <= 1) return n;
    if (auto it = cache.find(n); it != cache.end()) return it->second;
    return cache[n] = fib(n - 1, cache) + fib(n - 2, cache);
}

int main() {
    std::unordered_map<int, unsigned long long> cache;
    for (int i = 0; i < 10; i++) std::cout << fib(i, cache) << ' ';
    std::cout << '\n' << fib(50, cache) << '\n';
}

The plain version fib(n-1) + fib(n-2) repeats the same work and is very slow for big n. Saving the answers (memoization) makes it fast.

Sum of digits and binary search

#include <iostream>
#include <vector>

int digit_sum(int n) {
    return n == 0 ? 0 : n % 10 + digit_sum(n / 10);
}

int binary_search(const std::vector<int>& v, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (v[mid] == target) return mid;
    return v[mid] < target ? binary_search(v, target, mid + 1, hi) : binary_search(v, target, lo, mid - 1);
}

int main() {
    std::cout << digit_sum(9475) << '\n';
    std::vector<int> v = {2, 5, 8, 12, 16, 23, 38};
    std::cout << binary_search(v, 23, 0, static_cast<int>(v.size()) - 1) << '\n';
}

Deep recursion crashes

Every call uses space on the stack. A recursion without a base case (or a very deep one) causes a stack overflow, and the program crashes. C++ does not catch it with an exception.

Recursion or loop?

• A loop is faster and uses less memory.
• Recursion is clearer for trees, folders, backtracking and divide and conquer.
• The compiler may optimize some recursion, but it is not guaranteed.

• Previous Page
• Next Page

---

Exercises & Assignments
No Content Found.

Interview Questions & Answers
No Content Found.