📌 Recursion: Principles of Recursion

1️⃣ What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It breaks a problem into smaller subproblems until it reaches a base condition.

Example: Factorial Using Recursion

c
#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1;  // Base case
    return n * factorial(n - 1);  // Recursive case
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

🔹 Output:

csharp
Factorial of 5 is 120

---

2️⃣ Principles of Recursion

(a) Base Case (Termination Condition)

A base case is the condition where recursion stops. Without it, recursion runs infinitely, causing a stack overflow.

🔹 Example: In the factorial function, the base case is:

c
if (n == 0) return 1;

(b) Recursive Case (Self-Call with Reduced Problem Size)

Each recursive call reduces the problem size and moves toward the base case.

c
return n * factorial(n - 1);

(c) Stack Memory Usage

Each recursive call stores its state in the call stack. When the base case is reached, calls start returning results.

🔹 Example: Recursive Stack for factorial(5)

scss
factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0)

Each function call waits for the next call to return its value.

---

3️⃣ Types of Recursion

(a) Direct Recursion

A function calls itself directly.

c
void func() {
    func();  // Direct call
}

(b) Indirect Recursion

A function calls another function, which calls it back.

c
void A() { B(); }
void B() { A(); }

(c) Tail Recursion

The recursive call is the last operation before returning.

c
void tailRecursion(int n) {
    if (n == 0) return;
    printf("%d ", n);
    tailRecursion(n - 1);  // Last operation
}

🔹 More memory-efficient than normal recursion.

---

4️⃣ Common Recursion Problems

(a) Fibonacci Series

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

(b) Sum of Digits

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

(c) Reverse a String

c
void reverseString(char str[], int start, int end) {
    if (start >= end) return;
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;
    reverseString(str, start + 1, end - 1);
}

---

5️⃣ Recursion vs Iteration

Aspect	Recursion	Iteration
Memory Usage	High (Stack)	Low
Speed	Slower (Function Calls)	Faster
Code Simplicity	More Elegant	More Efficient
Example	Factorial using recursion	Factorial using loop

---

6️⃣ When to Use Recursion?

✅ Problems with natural recursive structure (Trees, DFS, Fibonacci).
✅ When code clarity is more important than performance.
✅ When stack space is not a constraint.

🚀 Do you prefer recursion or loops? Let’s discuss! ⬇️