C# Recursion

Recursion Fundamentals

if (n == 0)
    return 1; // Stop here

return n * Factorial(n - 1);
// Calls itself

Sum(5) → Sum(4) → Sum(3)
// Gets simpler

// Too many calls can
// cause stack overflow

🔹 Simple Recursion Example

Recursion occurs when a method calls itself to solve a smaller instance of the same problem. A classic beginner example is a countdown function: def Countdown(n): if n <= 0: return; else: print(n); Countdown(n-1). Each call reduces `n` by 1 until the base case (`n <= 0`) is reached, stopping the recursion. This visually demonstrates the call stack building up and then unwinding, forming the foundational concept for solving more complex problems like tree traversals and divide-and-conquer algorithms.

class Program
{
    static void Countdown(int number)
    {
        // Base case - stop when we reach 0
        if (number <= 0)
        {
            Console.WriteLine("Done!");
            return;
        }
        
        // Print current number
        Console.WriteLine(number);
        
        // Recursive call with smaller number
        Countdown(number - 1);
    }
    
    static void Main(string[] args)
    {
        Console.WriteLine("Countdown from 5:");
        Countdown(5);
    }
}

// Output:
// Countdown from 5:
// 5
// 4
// 3
// 2
// 1
// Done!

Countdown from 5:
5
4
3
2
1
Done!

🔹 Factorial Calculation

The factorial of a non-negative integer n (n!) is the product of all positive integers less than or equal to n. It's defined recursively as: n! = n * (n-1)!, with the base case 0! = 1. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120. A recursive method mirrors this definition: int Factorial(int n) { if (n <= 1) return 1; return n * Factorial(n-1); }. This elegantly expresses the mathematical definition but requires awareness of stack overflow risks for large `n`.

class Program
{
    static int Factorial(int n)
    {
        // Base case: factorial of 0 or 1 is 1
        if (n <= 1)
        {
            return 1;
        }
        
        // Recursive case: n! = n × (n-1)!
        return n * Factorial(n - 1);
    }
    
    static void Main(string[] args)
    {
        Console.WriteLine("5! = " + Factorial(5));
        Console.WriteLine("4! = " + Factorial(4));
        Console.WriteLine("3! = " + Factorial(3));
        Console.WriteLine("1! = " + Factorial(1));
    }
}

// How it works for Factorial(5):
// Factorial(5) = 5 * Factorial(4)
// Factorial(4) = 4 * Factorial(3)
// Factorial(3) = 3 * Factorial(2)
// Factorial(2) = 2 * Factorial(1)
// Factorial(1) = 1 (base case)
// Result: 5 * 4 * 3 * 2 * 1 = 120

// Output:
// 5! = 120
// 4! = 24
// 3! = 6
// 1! = 1

5! = 120
4! = 24
3! = 6
1! = 1

🔹 Sum of Numbers

Calculating the sum of numbers from 1 to n recursively demonstrates how recursion can replace iterative loops. The logic: The sum of 1 to n is `n` plus the sum of 1 to `n-1`. The base case is when `n` is 1, the sum is simply 1. Code: int Sum(int n) { if (n == 1) return 1; return n + Sum(n - 1); }. While a `for` loop might be more efficient here, this example clearly illustrates the recursive thought process: breaking a problem down into a smaller sub-problem of the same type until a trivial base case is solved.

class Program
{
    static int Sum(int n)
    {
        // Base case: sum of 0 is 0
        if (n <= 0)
        {
            return 0;
        }
        
        // Recursive case: n + sum of (n-1)
        return n + Sum(n - 1);
    }
    
    static void Main(string[] args)
    {
        Console.WriteLine("Sum 1 to 5: " + Sum(5));
        Console.WriteLine("Sum 1 to 10: " + Sum(10));
        Console.WriteLine("Sum 1 to 3: " + Sum(3));
    }
}

// How it works for Sum(5):
// Sum(5) = 5 + Sum(4)
// Sum(4) = 4 + Sum(3)
// Sum(3) = 3 + Sum(2)
// Sum(2) = 2 + Sum(1)
// Sum(1) = 1 + Sum(0)
// Sum(0) = 0 (base case)
// Result: 5 + 4 + 3 + 2 + 1 = 15

// Output:
// Sum 1 to 5: 15
// Sum 1 to 10: 55
// Sum 1 to 3: 6

Sum 1 to 5: 15
Sum 1 to 10: 55
Sum 1 to 3: 6

🔹 Power Calculation

Raising a base to an exponent recursively breaks the problem into repeated multiplication. The definition: power(base, exp) = base * power(base, exp-1), with the base case power(base, 0) = 1. Code: double Power(double base, int exp) { if (exp == 0) return 1; return base * Power(base, exp - 1); }. For example, Power(2, 3) calculates as `2 * Power(2,2)` -> `2 * 2 * Power(2,1)` -> `2 * 2 * 2 * 1 = 8`. This is intuitive but note that more efficient recursive algorithms (like exponentiation by squaring) exist for large exponents.

class Program
{
    static int Power(int baseNum, int exponent)
    {
        // Base case: any number to power 0 is 1
        if (exponent == 0)
        {
            return 1;
        }
        
        // Recursive case: base × base^(exponent-1)
        return baseNum * Power(baseNum, exponent - 1);
    }
    
    static void Main(string[] args)
    {
        Console.WriteLine("2^3 = " + Power(2, 3));
        Console.WriteLine("5^2 = " + Power(5, 2));
        Console.WriteLine("3^4 = " + Power(3, 4));
        Console.WriteLine("10^0 = " + Power(10, 0));
    }
}

// How it works for Power(2, 3):
// Power(2, 3) = 2 * Power(2, 2)
// Power(2, 2) = 2 * Power(2, 1)
// Power(2, 1) = 2 * Power(2, 0)
// Power(2, 0) = 1 (base case)
// Result: 2 * 2 * 2 * 1 = 8

// Output:
// 2^3 = 8
// 5^2 = 25
// 3^4 = 81
// 10^0 = 1

2^3 = 8
5^2 = 25
3^4 = 81
10^0 = 1

🔹 Fibonacci Sequence

The Fibonacci sequence is a famous series where each number is the sum of the two preceding ones, starting from 0 and 1. Recursively: Fib(n) = Fib(n-1) + Fib(n-2), with base cases Fib(0)=0 and Fib(1)=1. Code: int Fibonacci(int n) { if (n <= 1) return n; return Fibonacci(n-1) + Fibonacci(n-2); }. While elegant, this naive recursion has exponential time complexity because it recalculates the same values repeatedly. It's a prime example to introduce memoization or dynamic programming for optimization.

class Program
{
    static int Fibonacci(int n)
    {
        // Base cases
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // Recursive case: sum of previous two numbers
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    
    static void Main(string[] args)
    {
        Console.WriteLine("First 8 Fibonacci numbers:");
        for (int i = 0; i < 8; i++)
        {
            Console.Write(Fibonacci(i) + " ");
        }
        Console.WriteLine();
        
        Console.WriteLine("\nFibonacci(6) = " + Fibonacci(6));
    }
}

// How it works for Fibonacci(5):
// Fib(5) = Fib(4) + Fib(3)
// Fib(4) = Fib(3) + Fib(2)
// Fib(3) = Fib(2) + Fib(1)
// Fib(2) = Fib(1) + Fib(0)
// Fib(1) = 1, Fib(0) = 0 (base cases)

// Output:
// First 8 Fibonacci numbers:
// 0 1 1 2 3 5 8 13
//
// Fibonacci(6) = 8

First 8 Fibonacci numbers:
0 1 1 2 3 5 8 13

Fibonacci(6) = 8

🔹 Recursion vs Iteration

Both recursion and iteration (loops) can solve repetitive problems, but with different trade-offs. Recursion often leads to cleaner, more readable code that closely mirrors the problem's mathematical definition, especially for tree/graph traversals or divide-and-conquer. However, it risks stack overflow for deep recursion and can have higher memory overhead. Iteration is generally more memory-efficient and faster, but code for complex problems can become less intuitive. The choice depends on the problem nature, performance requirements, and readability priorities.

class Program
{
    // Recursive approach
    static int FactorialRecursive(int n)
    {
        if (n <= 1) return 1;
        return n * FactorialRecursive(n - 1);
    }
    
    // Iterative approach
    static int FactorialIterative(int n)
    {
        int result = 1;
        for (int i = 2; i <= n; i++)
        {
            result *= i;
        }
        return result;
    }
    
    static void Main(string[] args)
    {
        Console.WriteLine("Recursive: " + FactorialRecursive(5));
        Console.WriteLine("Iterative: " + FactorialIterative(5));
    }
}

// Output:
// Recursive: 120
// Iterative: 120

Recursive: 120
Iterative: 120

🔹 Important Recursion Rules

Writing correct recursive methods requires adhering to three fundamental rules to avoid infinite loops and logic errors. First, a recursive method must have a Base Case—a condition where it returns without making a recursive call. Second, it must make progress toward the base case with each call (e.g., by reducing a parameter). Third, the method must call itself. Violating any rule typically causes a stack overflow. Additionally, understanding the call stack and considering tail recursion (where the recursive call is the last operation) for compiler optimization are advanced but important concepts.

// ✓ Good recursion - has base case
static int GoodRecursion(int n)
{
    if (n <= 0) return 0; // Base case
    return n + GoodRecursion(n - 1); // Moves toward base
}

// ✗ Bad recursion - no base case!
static int BadRecursion(int n)
{
    return n + BadRecursion(n - 1); // Never stops!
    // This will cause StackOverflowException
}