Recursion

Sum of first N naturals

• sum(n) = n + sum(n-1), base sum(0)=0.
• **Real-life:** total score after n rounds if you add the latest round to the sum of previous rounds.

int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}
// sum(5) = 15

Direct vs indirect recursion

• **Direct:** f calls f.
• **Indirect:** f calls g, and g calls f (or a longer cycle).
• Same rules: clear base cases and progress toward termination.

bool isEven(int n);
bool isOdd(int n);

bool isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);
}
bool isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);
}

Tail recursion and stack pressure

• A **tail-recursive** call is the last action in the function — some languages optimize it; C++ does **not** guarantee TCO.
• Deep recursion on large n can still overflow — use iteration or increase design limits carefully.
• Naive Fibonacci is exponential time — add **memoization** (cache results) or use a loop.

#include <vector>
using namespace std;

long long fibMemo(int n, vector<long long>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

Backtracking pattern (application)

• Choose an option → recurse → undo the choice (backtrack) → try next option.
• **Real-life:** maze — walk a path, hit a dead end, step back, try another corridor.
• Used in N-Queens, permutations, subset sum, crossword-like fills.

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

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

Tree recursion (application idea)

• A tree node’s work often = process node + recurse(left) + recurse(right).
• **Real-life:** company org chart — total headcount(manager) = 1 + sum(headcount(report)).
• **Real-life:** disk usage — folder size = file sizes + size of subfolders.

Safety checklist

• Always write the base case first.
• Ensure every recursive path moves closer to the base (smaller n, narrower range, shorter string).
• Test n=0, n=1, and one medium value with a paper trace.
• Watch integer overflow for factorial / fib of larger inputs (long long).
• If depth may be thousands+, prefer iteration or an explicit stack.

Factorial

#include <iostream>
using namespace std;

long long fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

int main() {
    cout << fact(6) << "\n"; // 720
    return 0;
}

Fibonacci print first N terms

#include <iostream>
using namespace std;

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int n = 8;
    for (int i = 0; i < n; i++) cout << fib(i) << " ";
    return 0;
}

Sum of digits (recursive)

#include <iostream>
using namespace std;

int sumDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumDigits(n / 10);
}

int main() {
    cout << sumDigits(1234) << "\n"; // 10
    return 0;
}

Power x^n (recursive)

#include <iostream>
using namespace std;

long long power(long long x, int n) {
    if (n == 0) return 1;
    return x * power(x, n - 1);
}

int main() {
    cout << power(2, 10) << "\n"; // 1024
    return 0;
}

Tower of Hanoi (n = 3)

#include <iostream>
using namespace std;

void hanoi(int n, char a, char c, char b) {
    if (n == 0) return;
    hanoi(n - 1, a, b, c);
    cout << "Move " << n << ": " << a << " -> " << c << "\n";
    hanoi(n - 1, b, c, a);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

GCD — Euclid recursion

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    cout << gcd(84, 30) << "\n"; // 6
    return 0;
}

Recursive binary search

#include <iostream>
using namespace std;

int bsearch(int a[], int lo, int hi, int key) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == key) return mid;
    if (key < a[mid]) return bsearch(a, lo, mid - 1, key);
    return bsearch(a, mid + 1, hi, key);
}

int main() {
    int a[] = {2, 4, 6, 8, 10, 12};
    cout << bsearch(a, 0, 5, 10) << "\n";
    return 0;
}