#include <iostream>
#include <string>

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

int power(int b, int e) {              // fast exponentiation: O(log e)
    if (e == 0) return 1;
    int half = power(b, e / 2);
    return e % 2 ? half * half * b : half * half;
}

bool isPalindrome(const std::string& s, int l, int r) {
    if (l >= r) return true;
    return s[l] == s[r] && isPalindrome(s, l + 1, r - 1);
}

int main() {
    std::cout << factorial(20) << '\n';
    std::cout << power(3, 13) << '\n';
    std::cout << isPalindrome("racecar", 0, 6) << isPalindrome("rocket", 0, 5) << '\n';
}

2432902008176640000
1594323
10

#include <iostream>
#include <vector>

void subsets(const std::vector<int>& nums, std::size_t i, std::vector<int>& cur) {
    if (i == nums.size()) {
        std::cout << '{';
        for (int x : cur) std::cout << x;
        std::cout << "} ";
        return;
    }
    subsets(nums, i + 1, cur);          // exclude nums[i]
    cur.push_back(nums[i]);             // include nums[i]
    subsets(nums, i + 1, cur);
    cur.pop_back();                     // undo (backtrack)
}

int main() {
    std::vector<int> cur;
    subsets({1, 2, 3}, 0, cur);
    std::cout << '\n';
}

{} {3} {2} {23} {1} {13} {12} {123}

#include <iostream>
#include <vector>

long long fib(int n, std::vector<long long>& memo) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];          // already computed
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

int main() {
    std::vector<long long> memo(91, -1);
    std::cout << fib(90, memo) << '\n';          // instant; naive recursion would take ages
}

2880067194370816120