Meet C# Recursion: Self-Calling Methods Explained

Recursion is a programming technique many beginning developers are afraid of and I hope they won't be asked about it during the interview. After going through the explanation below, you will discover that it really is not as difficult as you might think. It is always good to have it in your “programming arsenal” and use it when needed.

Recursion

Recursion is simply a method that calls itself over and over until a certain criteria is met. As opposed to iteration, the solution of this approach depends on solutions to smaller instances of the same problem.

"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."

Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall

Recursion comes with several advantages and disadvantages, so it is definitely not always the right solution. Developers should use it wisely and don't overuse it. It helps to beautifully handle some certain complex problems such as tree traversing or exploring hierarchical data structures, so it is always good to know the right time to use it.

Advantages

The key advantage of recursion is that it is the only elegant approach to solve some problems, so it reduces the overall time complexity of the program.

Drawbacks

The biggest disadvantage is the increased memory usage because the call stack increases with every single method call, so the StackOverflowException might be thrown if not implemented properly. Recursion is also usually slower compared to iterative solutions, but this is not always the case. Also, recursion is more difficult to understand.

Common problems

The following are the most common problems that can be elegantly solved using recursion:

• Problems based on computing factorials
• Traversing/exploring trees and hierarchical data structures
• Tower of Henoi 

 

Example

Computing factorials is probably the most basic and easiest way to show the recursive principle in action.

As we know, a factorial of n is the product of all positive integers less than or equal to n. For example:

0! = 1
1! = 1
4! = 4 * 3 * 2 * 1 = 24
therefore:
n! = n * (n - 1)!

 As said before, every problem based on recursion can be solved with iterations as well. Therefore, let's go through the iterative method first:

private static long FactorialIterative(int n)
{
    if (n < 0)
        throw new ArithmeticException("Cannot compute factorial of negative integer");

    if (n == 0)
        return 1;

    long value = 1;
    for (int i = n; i > 0; i--)
        value *= i;

    return value;
}

Now let's go through the recursive version of the code above. As you can see, it is much shorter and easier to understand. As a matter of fact, the entire factorial computation can be elegantly written in just three lines of code.

Please pay close attention to line 7. This is the condition (criteria) that stops the method from calling itself. Every recursion must contain some protection, otherwise an infinite loop will be created and the application will crash for a lack of resources.

private static long FactorialRecursive(int n)
{
   if (n < 0)
      throw new ArithmeticException("Cannot compute factorial of negative integer");

   //the fence - once the condition is met, the method won't call itself again
   if (n == 0)
      return 1;

   return n * FactorialRecursive(n - 1);
}

To verify that the outputs of both methods are the same, we are going to compute a few factorials and write the results to the console:

Console.WriteLine("Iterative approach: 0! = {0}", FactorialIterative(0));
Console.WriteLine("Iterative approach: 1! = {0}", FactorialIterative(1));
Console.WriteLine("Iterative approach: 3! = {0}", FactorialIterative(3));
Console.WriteLine("Iterative approach: 5! = {0}", FactorialIterative(5));
Console.WriteLine("Iterative approach: 8! = {0}", FactorialIterative(8));
Console.WriteLine("Iterative approach: 10! = {0}", FactorialIterative(10));

Console.WriteLine("Recursive approach: 0! = {0}", FactorialRecursive(0));
Console.WriteLine("Recursive approach: 1! = {0}", FactorialRecursive(1));
Console.WriteLine("Recursive approach: 3! = {0}", FactorialRecursive(3));
Console.WriteLine("Recursive approach: 5! = {0}", FactorialRecursive(5));
Console.WriteLine("Recursive approach: 8! = {0}", FactorialRecursive(8));
Console.WriteLine("Recursive approach: 10! = {0}", FactorialRecursive(10));

The console output:

 

Figure 1: result

Conclusion

Recursion is an important approach that is not complicated at all and every developer should be aware of it. All the recursive method does is to call itself, usually many times until certain criteria are met. It is clearly not suited for every problem, but it is more than helpful when traversing data trees and other hierarchical structures.