Recursion on Strings and Fast Power

Peel off one piece

Handle one item yourself and let recursion handle the rest:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int total(const vector<int>& v, int i) {          // sum of v[i..end]
    if (i == (int)v.size()) return 0;
    return v[i] + total(v, i + 1);
}

string reverseStr(const string& s) {
    if (s.size() <= 1) return s;
    return reverseStr(s.substr(1)) + s[0];
}

int main() {
    cout << total({3, 1, 4, 1, 5}, 0) << endl;
    cout << reverseStr("stressed") << endl;
    return 0;
}

Output

14
desserts

Cut the problem in half

To work out 2¹⁰, work out 2⁵ once and square it. That takes about log₂(exp) calls instead of exp multiplications:

#include <iostream>
using namespace std;

long long power(long long base, int exp) {
    if (exp == 0) return 1;
    long long half = power(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    return half * half * base;
}

int main() {
    cout << power(2, 10) << " " << power(3, 13) << " " << power(2, 62) << endl;
    return 0;
}

Output

1024 1594323 4611686018427387904