C# Recursion

Recursion is the technique of making a function call itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.

Recursion may seem a bit difficult to understand. The best way to figure out how it works is to experiment with it.

Recursion Example

Adding two numbers together is easy to do, but adding a range of numbers is more complicated. In the following example, recursion is used to add a range of numbers together by breaking it down into the simple task of adding two numbers:

Examples

Basic Recursion

Adding numbers up to 10.

using System;

class Program
{
  static void Main(string[] args)
  {
    int result = Sum(10);
    Console.WriteLine(result);
  }

  static int Sum(int k) 
  {
    if (k > 0) 
    {
      return k + Sum(k - 1);
    } 
    else 
    {
      return 0;
    }
  }
}

Factorial

Calculating 5!

using System;

class Program
{
    static int Factorial(int n)
    {
        if (n == 0) return 1;
        return n * Factorial(n - 1);
    }
    
    static void Main()
    {
        Console.WriteLine(Factorial(5)); // 5*4*3*2*1 = 120
    }
}

Fibonacci Sequence

Classic recursive problem.

using System;

class Program
{
    static int Fibonacci(int n)
    {
        if (n <= 1) return n;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    
    static void Main()
    {
        Console.WriteLine(Fibonacci(10)); // 55
    }
}

Stopping Condition

Recursion needs a base case to stop.

using System;

class Program
{
  static int Count(int n)
  {
      if (n <= 0) return 0; // Base case
      Console.WriteLine(n);
      return Count(n - 1);
  }

  static void Main()
  {
      Count(3);
  }
}