C++ Recursion: Complete Guide with Examples

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

// Fibonacci function prototypes
int fibonacciIterative(int n);
int fibonacciRecursive(int n);
int fibonacciMemoization(int n);
int fibonacciDP(int n);
void printFibonacciComparison(int terms);

int main() {
    cout << "=== FIBONACCI SEQUENCE: MULTIPLE APPROACHES ===" << endl << endl;
    
    // First 15 Fibonacci numbers
    cout << "First 15 Fibonacci numbers:" << endl;
    printFibonacciComparison(15);
    
    cout << endl << "==========================================" << endl << endl;
    
    // Performance comparison for larger n
    cout << "Performance Comparison (n=30):" << endl;
    cout << "Note: Naive recursion becomes extremely slow!" << endl << endl;
    
    int n = 30;
    
    // 1. Iterative (fastest)
    auto start = high_resolution_clock::now();
    int iterResult = fibonacciIterative(n);
    auto stop = high_resolution_clock::now();
    auto iterTime = duration_cast<microseconds>(stop - start);
    
    // 2. Memoization (optimized recursion)
    start = high_resolution_clock::now();
    int memoResult = fibonacciMemoization(n);
    stop = high_resolution_clock::now();
    auto memoTime = duration_cast<microseconds>(stop - start);
    
    // 3. Dynamic Programming
    start = high_resolution_clock::now();
    int dpResult = fibonacciDP(n);
    stop = high_resolution_clock::now();
    auto dpTime = duration_cast<microseconds>(stop - start);
    
    // 4. Naive Recursive (VERY SLOW for n=30)
    cout << "Warning: Naive recursive Fibonacci(30) takes significant time..." << endl;
    start = high_resolution_clock::now();
    int recurResult = fibonacciRecursive(n);
    stop = high_resolution_clock::now();
    auto recurTime = duration_cast<milliseconds>(stop - start);
    
    cout << endl << "Results for Fibonacci(" << n << "):" << endl;
    cout << "All methods should give: " << iterResult << endl << endl;
    
    cout << "Performance Summary:" << endl;
    cout << "1. Iterative:      " << iterTime.count() << " microseconds" << endl;
    cout << "2. Memoization:    " << memoTime.count() << " microseconds" << endl;
    cout << "3. Dynamic Prog:   " << dpTime.count() << " microseconds" << endl;
    cout << "4. Naive Recursion: " << recurTime.count() << " milliseconds" << endl;
    
    cout << endl << "==========================================" << endl << endl;
    
    // Demonstration of why naive recursion is slow
    cout << "Why Naive Recursion is Slow for Fibonacci:" << endl;
    cout << "fib(5) = fib(4) + fib(3)" << endl;
    cout << "fib(4) = fib(3) + fib(2)" << endl;
    cout << "fib(3) = fib(2) + fib(1)" << endl;
    cout << "Notice fib(3) is calculated twice!" << endl;
    cout << "For fib(30), same values are recalculated millions of times!" << endl;
    
    return 0;
}

// ITERATIVE FIBONACCI (Most efficient)
int fibonacciIterative(int n) {
    if (n < 0) return -1; // Error
    if (n <= 1) return n;
    
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

// NAIVE RECURSIVE FIBONACCI (Inefficient - O(2^n))
int fibonacciRecursive(int n) {
    if (n < 0) return -1; // Error
    if (n <= 1) return n;
    
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// MEMOIZATION (Optimized recursion - O(n))
int fibonacciMemoHelper(int n, vector<int>& memo) {
    if (n <= 1) return n;
    
    // If already calculated, return cached value
    if (memo[n] != -1) {
        return memo[n];
    }
    
    // Calculate and store in memo
    memo[n] = fibonacciMemoHelper(n - 1, memo) + fibonacciMemoHelper(n - 2, memo);
    return memo[n];
}

int fibonacciMemoization(int n) {
    if (n < 0) return -1;
    
    vector<int> memo(n + 1, -1); // Initialize with -1 (not calculated)
    return fibonacciMemoHelper(n, memo);
}

// DYNAMIC PROGRAMMING (Bottom-up approach)
int fibonacciDP(int n) {
    if (n < 0) return -1;
    if (n <= 1) return n;
    
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

void printFibonacciComparison(int terms) {
    cout << "n\tIterative\tRecursive\tMemoization\tDP" << endl;
    cout << "-\t---------\t---------\t-----------\t--" << endl;
    
    for (int i = 0; i < terms; i++) {
        cout << i << "\t" 
             << fibonacciIterative(i) << "\t\t"
             << fibonacciRecursive(i) << "\t\t"
             << fibonacciMemoization(i) << "\t\t"
             << fibonacciDP(i) << endl;
    }
}

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

// Function to visualize recursion depth
void printIndent(int depth) {
    for (int i = 0; i < depth; i++) {
        cout << "|   ";
    }
}

// Factorial with stack visualization
long long factorialVisual(int n, int depth = 0) {
    printIndent(depth);
    cout << "→ factorial(" << n << ") called" << endl;
    
    if (n < 0) {
        printIndent(depth);
        cout << "← ERROR: Negative number!" << endl;
        throw invalid_argument("Negative number");
    }
    
    if (n <= 1) {
        printIndent(depth);
        cout << "← BASE CASE: returning 1" << endl;
        return 1;
    }
    
    printIndent(depth);
    cout << "   Need to calculate " << n << " * factorial(" << n-1 << ")" << endl;
    
    // Recursive call
    long long smallerFact = factorialVisual(n - 1, depth + 1);
    
    long long result = n * smallerFact;
    
    printIndent(depth);
    cout << "← factorial(" << n << ") = " << n << " * " << smallerFact 
         << " = " << result << endl;
    
    return result;
}

// Fibonacci with stack visualization (naive version)
int fibonacciVisual(int n, int depth = 0) {
    printIndent(depth);
    cout << "→ fibonacci(" << n << ") called" << endl;
    
    if (n < 0) {
        printIndent(depth);
        cout << "← ERROR: Negative number!" << endl;
        return -1;
    }
    
    if (n <= 1) {
        printIndent(depth);
        cout << "← BASE CASE: returning " << n << endl;
        return n;
    }
    
    printIndent(depth);
    cout << "   Need fibonacci(" << n-1 << ") + fibonacci(" << n-2 << ")" << endl;
    
    // Two recursive calls - demonstrates exponential growth
    int fib1 = fibonacciVisual(n - 1, depth + 1);
    
    printIndent(depth);
    cout << "   Got fibonacci(" << n-1 << ") = " << fib1 
         << ", now need fibonacci(" << n-2 << ")" << endl;
    
    int fib2 = fibonacciVisual(n - 2, depth + 1);
    
    int result = fib1 + fib2;
    
    printIndent(depth);
    cout << "← fibonacci(" << n << ") = " << fib1 << " + " << fib2 
         << " = " << result << endl;
    
    return result;
}

int main() {
    cout << "=== RECURSION STACK VISUALIZATION ===" << endl << endl;
    
    // Example 1: Factorial visualization
    cout << "Example 1: factorialVisual(5)" << endl;
    cout << "Call stack visualization:" << endl;
    cout << "==========================" << endl;
    long long fact5 = factorialVisual(5);
    cout << "==========================" << endl;
    cout << "Final result: " << fact5 << endl;
    
    cout << endl << "=====================================" << endl << endl;
    
    // Example 2: Fibonacci visualization (small n)
    cout << "Example 2: fibonacciVisual(4)" << endl;
    cout << "Call stack visualization:" << endl;
    cout << "==========================" << endl;
    cout << "Note: Same values are recalculated!" << endl;
    int fib4 = fibonacciVisual(4);
    cout << "==========================" << endl;
    cout << "Final result: " << fib4 << endl;
    
    cout << endl << "=====================================" << endl << endl;
    
    // Example 3: Stack overflow demonstration
    cout << "Example 3: Stack Overflow Risk" << endl;
    cout << "Trying factorialVisual(10000)..." << endl;
    
    try {
        // This will likely cause stack overflow
        // long long hugeFact = factorialVisual(10000);
        // cout << "Result: " << hugeFact << endl;
        cout << "(Commented out to prevent crash)" << endl;
    } catch (const exception& e) {
        cout << "Error: " << e.what() << endl;
    }
    
    cout << endl << "Recursive calls create stack frames." << endl;
    cout << "Each frame contains:" << endl;
    cout << "1. Parameters" << endl;
    cout << "2. Local variables" << endl;
    cout << "3. Return address" << endl;
    cout << "4. Previous frame pointer" << endl;
    cout << endl << "Stack size is limited (typically 1-8 MB)" << endl;
    
    return 0;
}

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

// Tree node structure
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// Example 1: Binary Tree Traversal
TreeNode* createSampleTree() {
    // Create tree:       1
    //                  /   \
    //                 2     3
    //                / \   /
    //               4   5 6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    return root;
}

// Recursive In-order Traversal (Natural fit)
void inorderRecursive(TreeNode* node) {
    if (node == nullptr) return;
    
    inorderRecursive(node->left);
    cout << node->value << " ";
    inorderRecursive(node->right);
}

// Iterative In-order Traversal (More complex)
void inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* current = root;
    
    while (current != nullptr || !stk.empty()) {
        // Reach leftmost node
        while (current != nullptr) {
            stk.push(current);
            current = current->left;
        }
        
        current = stk.top();
        stk.pop();
        
        cout << current->value << " ";
        
        current = current->right;
    }
}

// Example 2: Directory-like structure
struct Directory {
    string name;
    vector<Directory*> subdirectories;
    vector<string> files;
    
    Directory(string n) : name(n) {}
};

// Recursive directory traversal (Natural)
void listDirectoryRecursive(Directory* dir, int depth = 0) {
    string indent(depth * 2, ' ');
    
    cout << indent << dir->name << "/" << endl;
    
    // List files
    for (const string& file : dir->files) {
        cout << indent << "  " << file << endl;
    }
    
    // Recursively list subdirectories
    for (Directory* subdir : dir->subdirectories) {
        listDirectoryRecursive(subdir, depth + 1);
    }
}

// Iterative directory traversal (Complex)
void listDirectoryIterative(Directory* root) {
    stack<pair<Directory*, int>> stk;
    stk.push({root, 0});
    
    while (!stk.empty()) {
        auto [current, depth] = stk.top();
        stk.pop();
        
        string indent(depth * 2, ' ');
        cout << indent << current->name << "/" << endl;
        
        // List files
        for (const string& file : current->files) {
            cout << indent << "  " << file << endl;
        }
        
        // Push subdirectories in reverse order for correct traversal
        for (auto it = current->subdirectories.rbegin(); 
             it != current->subdirectories.rend(); ++it) {
            stk.push({*it, depth + 1});
        }
    }
}

// Example 3: Simple array processing (Better with iteration)
int sumArrayIterative(const vector<int>& arr) {
    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    return sum;
}

int sumArrayRecursive(const vector<int>& arr, int index = 0) {
    if (index >= arr.size()) return 0;
    return arr[index] + sumArrayRecursive(arr, index + 1);
}

int main() {
    cout << "=== REAL-WORLD RECURSION vs ITERATION EXAMPLES ===" << endl << endl;
    
    // Example 1: Tree Traversal
    cout << "Example 1: Binary Tree In-order Traversal" << endl;
    TreeNode* tree = createSampleTree();
    
    cout << "Recursive: ";
    inorderRecursive(tree);
    cout << endl;
    
    cout << "Iterative: ";
    inorderIterative(tree);
    cout << endl;
    
    cout << "Verdict: Recursion is cleaner for tree traversal" << endl;
    
    cout << endl << "===========================================" << endl << endl;
    
    // Example 2: Directory Structure
    cout << "Example 2: Directory Structure Traversal" << endl;
    
    Directory* root = new Directory("root");
    root->files = {"readme.txt", "config.ini"};
    
    Directory* docs = new Directory("documents");
    docs->files = {"report.pdf", "notes.txt"};
    root->subdirectories.push_back(docs);
    
    Directory* pics = new Directory("pictures");
    pics->files = {"photo1.jpg", "photo2.jpg"};
    root->subdirectories.push_back(pics);
    
    Directory* vacation = new Directory("vacation");
    vacation->files = {"beach.jpg", "mountain.png"};
    pics->subdirectories.push_back(vacation);
    
    cout << "Recursive traversal:" << endl;
    listDirectoryRecursive(root);
    
    cout << endl << "Iterative traversal:" << endl;
    listDirectoryIterative(root);
    
    cout << "Verdict: Recursion is more natural for hierarchical structures" << endl;
    
    cout << endl << "===========================================" << endl << endl;
    
    // Example 3: Array Processing
    cout << "Example 3: Array Summation" << endl;
    vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    cout << "Iterative sum: " << sumArrayIterative(numbers) << endl;
    cout << "Recursive sum: " << sumArrayRecursive(numbers) << endl;
    
    cout << "Verdict: Iteration is simpler and more efficient for linear arrays" << endl;
    
    cout << endl << "===========================================" << endl << endl;
    
    // Cleanup
    // Note: In real code, properly delete allocated memory
    cout << "Decision Guidelines:" << endl;
    cout << "1. Use RECURSION for:" << endl;
    cout << "   • Tree/graph traversal" << endl;
    cout << "   • Divide and conquer algorithms" << endl;
    cout << "   • Backtracking problems" << endl;
    cout << "   • Hierarchical data structures" << endl;
    cout << endl;
    cout << "2. Use ITERATION for:" << endl;
    cout << "   • Simple loops/linear processing" << endl;
    cout << "   • Performance-critical code" << endl;
    cout << "   • When stack depth could be large" << endl;
    cout << "   • When recursion doesn't simplify code" << endl;
    
    return 0;
}

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

// ===== BAD PRACTICES =====

// BAD: Missing base case (will crash)
int badFactorial(int n) {
    // Missing: if (n <= 1) return 1;
    return n * badFactorial(n - 1); // Infinite recursion!
}

// BAD: Incorrect base case (may never reach)
int badSum(int n) {
    if (n == 1) return 1; // What about n=0? n=negative?
    return n + badSum(n - 1);
}

// BAD: No progress toward base case
int infiniteRecursion(int n) {
    if (n == 0) return 0;
    return infiniteRecursion(n); // Same n, never decreases!
}

// BAD: Using recursion for simple iteration
void printNumbersBad(int n) {
    if (n <= 0) return;
    printNumbersBad(n - 1);
    cout << n << " ";
    // Simple loop would be better: for(int i=1; i<=n; i++) cout< 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// GOOD: Using recursion for natural problems
struct FileNode {
    string name;
    bool isDirectory;
    vector<FileNode*> children;
    
    FileNode(string n, bool dir) : name(n), isDirectory(dir) {}
};

// Natural use of recursion: File system traversal
void listFilesRecursive(FileNode* node, int depth = 0) {
    string indent(depth * 2, ' ');
    cout << indent << node->name << (node->isDirectory ? "/" : "") << endl;
    
    if (node->isDirectory) {
        for (FileNode* child : node->children) {
            listFilesRecursive(child, depth + 1);
        }
    }
}

int main() {
    cout << "=== RECURSION: GOOD vs BAD PRACTICES ===" << endl << endl;
    
    // Good practices demonstration
    cout << "Good Practices Examples:" << endl;
    cout << "1. Proper factorial(5): " << goodFactorial(5) << endl;
    cout << "2. Tail recursive factorial(5): " << goodFactorialTail(5) << endl;
    cout << "3. Sum of digits(12345): " << sumDigits(12345) << endl;
    cout << "4. Iterative sum of digits(12345): " << sumDigitsIterative(12345) << endl;
    
    cout << endl << "Fibonacci with Memoization (n=40):" << endl;
    cout << "This would be impossible with naive recursion!" << endl;
    cout << "fibonacciMemoized(40) = " << fibonacciMemoized(40) << endl;
    
    cout << endl << "=====================================" << endl << endl;
    
    // Creating a sample file structure
    cout << "Natural Recursion Example: File System" << endl;
    
    FileNode* root = new FileNode("root", true);
    FileNode* docs = new FileNode("documents", true);
    FileNode* pics = new FileNode("pictures", true);
    
    root->children.push_back(docs);
    root->children.push_back(pics);
    root->children.push_back(new FileNode("readme.txt", false));
    
    docs->children.push_back(new FileNode("report.pdf", false));
    docs->children.push_back(new FileNode("notes.txt", false));
    
    pics->children.push_back(new FileNode("photo1.jpg", false));
    pics->children.push_back(new FileNode("photo2.jpg", false));
    
    FileNode* vacation = new FileNode("vacation", true);
    vacation->children.push_back(new FileNode("beach.jpg", false));
    pics->children.push_back(vacation);
    
    cout << "File structure:" << endl;
    listFilesRecursive(root);
    
    cout << endl << "=====================================" << endl << endl;
    
    cout << "Recursion Guidelines Summary:" << endl;
    cout << "✓ DO use recursion for:" << endl;
    cout << "   • Tree/graph traversal" << endl;
    cout << "   • Divide and conquer" << endl;
    cout << "   • Backtracking problems" << endl;
    cout << "   • When it simplifies code significantly" << endl;
    cout << endl;
    cout << "✓ DO NOT use recursion for:" << endl;
    cout << "   • Simple linear iteration" << endl;
    cout << "   • Performance-critical code" << endl;
    cout << "   • When recursion depth could be large" << endl;
    cout << "   • When iterative solution is equally clear" << endl;
    cout << endl;
    cout << "✓ ALWAYS:" << endl;
    cout << "   • Define a base case" << endl;
    cout << "   • Ensure progress toward base case" << endl;
    cout << "   • Consider stack limitations" << endl;
    cout << "   • Test with edge cases" << endl;
    cout << "   • Consider memoization for repeated calculations" << endl;
    
    // Cleanup (in real code, use smart pointers)
    delete root;
    delete docs;
    delete pics;
    
    return 0;
}