4.5 Recursion Basics

Let’s go over recursion basics in C# — a fundamental concept where a method calls itself to solve a problem.

---

📌 1. What is Recursion?

Recursion is a technique in programming where a method calls itself either directly or indirectly to solve smaller instances of a problem.

• Every recursive method needs:

  1. Base case → stops recursion

  2. Recursive case → calls the method again with a smaller problem

---

📌 2. Basic Syntax

[access_modifier] returnType MethodName(parameters)
{
    if (baseCondition)
        return baseValue; // Base case
    
    // Recursive case
    return MethodName(modifiedParameters);
}

---

📌 3. Example 1: Factorial (Direct Recursion)

Factorial of n: n! = n * (n-1) * ... * 1

public int Factorial(int n)
{
    if (n <= 1)         // Base case
        return 1;
    else
        return n * Factorial(n - 1);  // Recursive call
}
 
// Usage
Console.WriteLine(Factorial(5)); // Output: 120

• Base case: n <= 1

• Recursive case: n * Factorial(n-1)

---

📌 4. Example 2: Fibonacci Sequence

public int Fibonacci(int n)
{
    if (n == 0) return 0;      // Base case
    if (n == 1) return 1;      // Base case
    return Fibonacci(n - 1) + Fibonacci(n - 2); // Recursive call
}
 
// Usage
Console.WriteLine(Fibonacci(6)); // Output: 8

• Two base cases: n == 0 and n == 1

• Recursive call reduces problem size

---

📌 5. Key Points

1. Base Case is Mandatory

   • Without it, recursion continues indefinitely → StackOverflowException

2. Recursive Case Must Progress Towards Base Case

   • Each call should reduce the problem size

3. Stack Usage

   • Each recursive call is pushed onto the call stack

4. Tail Recursion

   • Last operation is the recursive call → can be optimized by compiler

---

📌 6. Example 3: Sum of Numbers Using Recursion

public int Sum(int n)
{
    if (n <= 0) return 0;        // Base case
    return n + Sum(n - 1);       // Recursive call
}
 
Console.WriteLine(Sum(5)); // Output: 15 (5+4+3+2+1)

---

📌 7. Advantages & Disadvantages

Advantages	Disadvantages
Code is concise & readable	Uses more stack memory
Natural fit for divide & conquer	Can cause StackOverflow
Ideal for problems like trees, graphs, factorial, Fibonacci	Sometimes iterative solution is faster

---

✅ Tip:

• Always define a clear base case.

• Use recursion for problems that can be broken into smaller similar problems.

• For performance, sometimes iteration is better for simple tasks like summing numbers.