C# -

Recursion

Recursion in C# is a technique where a method calls itself to solve a problem. It can simplify complex problems by breaking them down into smaller, more manageable sub-problems. This tutorial covers the basics of recursion, its use cases, and best practices, with detailed examples.

1. Understanding Recursion

A recursive method is a method that calls itself. Recursive methods must have a base case to stop the recursion; otherwise, they will run indefinitely and cause a stack overflow.

Basic Example: 
        
            namespace RecursionExamples;

class Program
{
    static void Main(string[] args)
    {
        int result = Factorial(5);
        Console.WriteLine($"Factorial of 5: {result}");
    }

    static int Factorial(int n)
    {
        if (n == 0)
            return 1;
        return n * Factorial(n - 1);
    }
}

2. Use Cases for Recursion

Recursion is commonly used in problems that can be divided into similar sub-problems, such as tree traversal, factorial calculation, Fibonacci sequence generation, and solving puzzles like the Towers of Hanoi.

Example 1: Factorial Calculation 
        
            namespace RecursionExamples;

class Program
{
    static void Main(string[] args)
    {
        int result = Factorial(5);
        Console.WriteLine($"Factorial of 5: {result}");
    }

    static int Factorial(int n)
    {
        if (n == 0)
            return 1;
        return n * Factorial(n - 1);
    }
}
Example 2: Fibonacci Sequence 
        
            namespace RecursionExamples;

class Program
{
    static void Main(string[] args)
    {
        int n = 10;
        for (int i = 0; i < n; i++)
        {
            Console.WriteLine($"Fibonacci({i}): {Fibonacci(i)}");
        }
    }

    static int Fibonacci(int n)
    {
        if (n <= 1)
            return n;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}
Example 3: Tree Traversal 
        
            using System;
using System.Collections.Generic;

namespace RecursionExamples;

class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(1)
        {
            Left = new TreeNode(2),
            Right = new TreeNode(3)
            {
                Left = new TreeNode(4),
                Right = new TreeNode(5)
            }
        };

        Console.WriteLine("Pre-order Traversal:");
        PreOrderTraversal(root);
    }

    static void PreOrderTraversal(TreeNode node)
    {
        if (node == null)
            return;

        Console.WriteLine(node.Value);
        PreOrderTraversal(node.Left);
        PreOrderTraversal(node.Right);
    }
}

class TreeNode
{
    public int Value { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }

    public TreeNode(int value)
    {
        Value = value;
    }
}

3. Best Practices for Recursion

4. Advanced Example: Towers of Hanoi

The Towers of Hanoi is a classic problem that demonstrates the power of recursion. The goal is to move a set of disks from one peg to another, using a third peg as a temporary holding area, following these rules:

Example: 
        
            namespace RecursionExamples;

class Program
{
    static void Main(string[] args)
    {
        int n = 3; // Number of disks
        TowersOfHanoi(n, 'A', 'C', 'B');
    }

    static void TowersOfHanoi(int n, char fromPeg, char toPeg, char auxPeg)
    {
        if (n == 1)
        {
            Console.WriteLine($"Move disk 1 from peg {fromPeg} to peg {toPeg}");
            return;
        }

        TowersOfHanoi(n - 1, fromPeg, auxPeg, toPeg);
        Console.WriteLine($"Move disk {n} from peg {fromPeg} to peg {toPeg}");
        TowersOfHanoi(n - 1, auxPeg, toPeg, fromPeg);
    }
}

Conclusion

Recursion is a valuable technique in C# programming, allowing complex problems to be solved elegantly by breaking them down into simpler sub-problems. This tutorial covered the basics of recursion, its use cases, and best practices, along with several detailed examples.