Skillversitas

Recursion in C++

Recursion is a programming technique in which a function calls itself to break a problem into smaller sub-problems. Every recursive function must have a base case (stopping condition) and a recursive case (calling itself with smaller input).

Without a correct base case, a recursive function will keep calling itself until the stack overflows. The base case determines when the recursion stops. The recursive case must approach the base case with every call.

Stack Frame

Every time a function is called (including recursive calls), a new stack frame is created in memory. A stack frame stores local parameters, local variables, and the return address. If the recursion is too deep, the stack fills up → stack overflow.

Factorial and Fibonacci

Two classic examples of recursion:
- Factorial: n! = n × (n-1)!, base case: 0! = 1
- Fibonacci: fib(n) = fib(n-1) + fib(n-2), base case: fib(0) = 0, fib(1) = 1

Tail Recursion

Tail recursion is recursion where the recursive call is the last operation in the function. Some compilers can optimize tail recursion into a loop (tail call optimization), avoiding stack overflow.

Code Example

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

// Factorial: iterative
long long factorialIterative(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

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

// Fibonacci: recursive (simple but slow)
long long fibRecursive(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// Fibonacci: iterative (efficient)
long long fibIterative(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

// Fibonacci: memoization (recursive + cache)
long long fibMemo(int n, vector<long long>& memo) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// Power: tail recursion
long long powerTail(long long base, int exponent, long long accumulator = 1) {
    if (exponent == 0) return accumulator;
    return powerTail(base, exponent - 1, accumulator * base);
}

// Power: regular recursion
long long powerRecursive(long long base, int exponent) {
    if (exponent == 0) return 1;
    return base * powerRecursive(base, exponent - 1);
}

// Tower of Hanoi
void hanoi(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        cout << "  Move disk 1 from " << source << " to " << target << endl;
        return;
    }
    hanoi(n - 1, source, auxiliary, target);
    cout << "  Move disk " << n << " from " << source << " to " << target << endl;
    hanoi(n - 1, auxiliary, target, source);
}

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

// Array sum
int sumArray(int arr[], int size) {
    if (size == 0) return 0;
    return arr[size - 1] + sumArray(arr, size - 1);
}

// Palindrome check
bool isPalindrome(const string& s, int start, int end) {
    if (start >= end) return true;
    if (s[start] != s[end]) return false;
    return isPalindrome(s, start + 1, end - 1);
}

// Recursive prime check
bool isPrimeRecursive(int n, int divisor) {
    if (n < 2) return false;
    if (divisor * divisor > n) return true;
    if (n % divisor == 0) return false;
    return isPrimeRecursive(n, divisor + 1);
}

// Ackermann function (double recursion)
int ackermann(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));
}

// Print the binary representation
void printBinary(int n) {
    if (n < 2) {
        cout << n;
        return;
    }
    printBinary(n / 2);
    cout << n % 2;
}

// Count digits
int countDigits(int n) {
    if (n < 10) return 1;
    return 1 + countDigits(n / 10);
}

// Greatest Common Divisor (Euclidean)
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    // Factorial
    cout << "--- Factorial ---" << endl;
    for (int i = 0; i <= 10; i++) {
        cout << i << "! = " << factorialRecursive(i) << endl;
    }

    // Fibonacci
    cout << "\n--- Fibonacci ---" << endl;
    cout << "Recursive (n=10): " << fibRecursive(10) << endl;
    cout << "Iterative (n=10): " << fibIterative(10) << endl;

    vector<long long> memo(50, -1);
    cout << "Memoization (n=10): " << fibMemo(10, memo) << endl;

    // Speed comparison
    cout << "\nFibonacci(30):" << endl;
    cout << "  Recursive: " << fibRecursive(30) << endl;
    cout << "  Iterative: " << fibIterative(30) << endl;
    memo.assign(50, -1);
    cout << "  Memo: " << fibMemo(30, memo) << endl;

    // Power
    cout << "\n--- Power ---" << endl;
    cout << "2^10 recursive: " << powerRecursive(2, 10) << endl;
    cout << "2^10 tail: " << powerTail(2, 10) << endl;

    // Tower of Hanoi
    cout << "\n--- Tower of Hanoi (3 disk) ---" << endl;
    hanoi(3, 'A', 'C', 'B');

    // Reverse a string
    cout << "\n--- Reverse String ---" << endl;
    string text = "HELLO";
    cout << text << " -> " << reverseStr(text) << endl;

    // Array sum
    cout << "\n--- Sum Array ---" << endl;
    int numbers[] = {1, 2, 3, 4, 5};
    cout << "Sum: " << sumArray(numbers, 5) << endl;

    // Palindrome
    cout << "\n--- Palindrome ---" << endl;
    string word1 = "MADAM";
    string word2 = "HELLO";
    cout << word1 << " palindrome? " << (isPalindrome(word1, 0, word1.length()-1) ? "Yes" : "No") << endl;
    cout << word2 << " palindrome? " << (isPalindrome(word2, 0, word2.length()-1) ? "Yes" : "No") << endl;

    // Prime numbers
    cout << "\n--- Prime Recursive ---" << endl;
    for (int i = 2; i <= 20; i++) {
        if (isPrimeRecursive(i, 2)) {
            cout << i << " ";
        }
    }
    cout << endl;

    // Ackermann
    cout << "\n--- Ackermann ---" << endl;
    cout << "A(2,1) = " << ackermann(2, 1) << endl;

    // Binary representation
    cout << "\n--- Binary ---" << endl;
    cout << "42 in binary: ";
    printBinary(42);
    cout << endl;

    // Count digits
    cout << "\n--- Count Digits ---" << endl;
    cout << "12345 has " << countDigits(12345) << " digits" << endl;

    // GCD
    cout << "\n--- GCD ---" << endl;
    cout << "GCD(48, 18) = " << gcd(48, 18) << endl;

    return 0;
}

Code Explanation

  • factorialRecursive(n) — Base case: n <= 1 returns 1. Recursive case: n * factorialRecursive(n-1). Example: 5! = 5 * 4!, 4! = 4 * 3!, and so on.
  • fibRecursive(n) — Two base cases: fib(0)=0, fib(1)=1. Recursive: fib(n-1) + fib(n-2). Simple but O(2^n) because many subproblems are recomputed.
  • fibMemo(n, memo) — Memoization: stores previous results in a vector. If already computed, it returns directly from the cache. Reduces the complexity from O(2^n) to O(n).
  • powerTail(base, exponent, accumulator) — Tail recursion: the recursive call is the last operation. The accumulator accumulates the multiplication step by step. It can be optimized by the compiler into a loop.
  • hanoi(n, source, target, auxiliary) — The Tower of Hanoi algorithm. Move n-1 disks to the auxiliary peg, move the largest disk to the target, then move n-1 disks from the auxiliary to the target. Complexity: 2^n - 1 moves.
  • reverseStr(s) — Reverses a string recursively. Base case: string length ≤ 1. Recursive: reverse of substr(1) + first character.
  • sumArray(arr, size) — Sums the array from the back. Base case: size == 0 returns 0. Recursive: arr[size-1] + sumArray(arr, size-1).
  • isPalindrome(s, start, end) — Checks a palindrome from the outside in. Matches the first and last characters, then proceeds to the inner pair.
  • isPrimeRecursive(n, divisor) — Checks divisors from 2 up to √n recursively.
  • ackermann(m, n) — A double-recursive function that grows very fast. A(2,1) = 5, A(3,3) = 61.
  • printBinary(n) — Prints the binary representation using recursion. Divide by 2, recurse on the quotient, print the remainder.
  • gcd(a, b) — The Euclidean algorithm. Base: b==0 returns a. Recursive: gcd(b, a%b).

Everyday Use Cases

File system traversal: Exploring folders recursively. Each folder can contain sub-folders that also need to be explored. Base case: the item is a file (not a folder).

Binary search: Searching for an element in a sorted array. Compare the middle element, then search the left or right half. Base case: the element is found or the range is empty.

Tower of Hanoi: Models moving disks in the classic puzzle. It also appears in the context of stack optimization in games and other puzzles.

Conclusion

Recursion is a powerful technique for breaking a problem into smaller sub-problems. Every recursive function must have a base case to prevent infinite recursion. Simple recursion can be inefficient (lots of repetition), but it can be optimized with memoization. Tail recursion allows the compiler to optimize it into a loop. Use recursion for problems that are naturally recursive, such as tree traversal, divide-and-conquer, and puzzles.