Recursion, DSA in C++

Recursion ek aisa programming concept hai jisme ek function khud ko call karta hai taaki problem ko chhote chhote parts mein solve kiya ja sake. Yeh algorithms like tree traversals, divide-and-conquer, aur dynamic programming mein bahut use hota hai.

1. Recursion Ka Basic Concept

Ek recursive function ke three important parts hote hain:

1. Base Case (Stop Condition): Yahan recursion rukta hai, warna infinite calls ho sakti hain.
2. Recursive Case (Khud Ko Call Karna): Function khud ko modify kiye hue inputs ke saath call karta hai.
3. Self Work: Self work mein ek small task hame karna hota hai jiske base par recursive calls chalti hai.

Example: Factorial Calculate Karna (n! = n × (n-1) × ... × 1)

#include <iostream>
using namespace std;

int factorial(int n) {
    // Base Case: Agar n = 0 ya 1, toh factorial 1 hota hai (simple math rule)
    if (n == 0 || n == 1) {
        return 1;
    }
    // Recursive Case: n * factorial(n-1)
    else {
        // Self Work: n*func()
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is: " << factorial(num) << endl;
    // Output: 120 (5! = 5 × 4 × 3 × 2 × 1 = 120)
    return 0;
}

Kya Hota Hai Internally?

1. factorial(5) calls 5 * factorial(4)
2. factorial(4) calls 4 * factorial(3)
3. factorial(3) calls 3 * factorial(2)
4. factorial(2) calls 2 * factorial(1)
5. factorial(1) returns 1 (base case)
6. Ab values wapas calculate hoti hain:

• 2 * 1 = 2
• 3 * 2 = 6
• 4 * 6 = 24
• 5 * 24 = 120

2. Recursion vs Iteration (Loop)

FeatureRecursionIteration (Loop)SpeedSlow (har call stack pe banta hai)Fast (no extra memory)MemoryMore (stack overflow ho sakta hai)Less (efficient)ReadabilityClean (short code)Sometimes complexUse CaseTrees, Backtracking, DPSimple loops, performance-critical

Example: Fibonacci Series (Recursion vs Loop)

(A) Recursive Approach (Exponential Time - O(2ⁿ))

cpp

Copy

Download

int fib(int n) {
    if (n <= 1) return n;  // Base case
    return fib(n - 1) + fib(n - 2);  // Recursive calls
}

Problem: Repeated calculations (e.g., fib(5) calls fib(4) + fib(3), then fib(3) again).

(B) Iterative Approach (Linear Time - O(n))

cpp

Copy

Download

int fib(int n) {
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Better: Faster, no stack overflow risk.

3. Types of Recursion

(1) Direct Recursion

Function directly calls itself.

cpp

Copy

Download

void fun() {
    fun();  // Direct call
}

(2) Indirect Recursion

Function A calls B, B calls A.

cpp

Copy

Download

void funA(int n) {
    if (n > 0) {
        cout << n << " ";
        funB(n - 1);  // Calls another function