C# Recursion Example

A recursive method calls itself. Many algorithms in the C# language involve recursion. Recursive methods are used extensively in programming and in compilers. They help with complex problems. They solve problems and puzzles with brute force. They exhaust all possibilities.

This C# tutorial shows how to develop algorithms based on recursion.

Example

Initially we look at a method that is a recursive method and calls itself in the C# language. The recursive method has two parameters, including a reference variable parameter. It checks a condition near the top of its method body, as many recursive algorithms do.

It calls itself again based on an incremented value of the parameter it receives. The program also contains a commented-out exception that demonstrates the appearance of the method call stack frames in a recursive algorithm.

Program that uses Recursive method [C#]

using System;

class Program
{
    static int Recursive(int value, ref int count)
    {
	count++;
	if (value >= 10)
	{
	    // throw new Exception("End");
	    return value;
	}
	return Recursive(value + 1, ref count);
    }

    static void Main()
    {
	//
	// Call recursive method with two parameters.
	//
	int count = 0;
	int total = Recursive(5, ref count);
	//
	// Write the result from the method calls and also the call count.
	//
	Console.WriteLine(total);
	Console.WriteLine(count);
    }
}

Output

10              Total value of 10 was added up.
6               Six method calls.

Exception thrown when throw uncommented

Unhandled Exception: System.Exception: End
   at Program.Recursive(Int32 value, Int32& count) ...Program.cs:line 10
   at Program.Recursive(Int32 value, Int32& count) ...Program.cs:line 13
   at Program.Recursive(Int32 value, Int32& count) ...Program.cs:line 13
   at Program.Recursive(Int32 value, Int32& count) ...Program.cs:line 13
   at Program.Recursive(Int32 value, Int32& count) ...Program.cs:line 13
   at Program.Recursive(Int32 value, Int32& count) ...Program.cs:line 13
   at Program.Main() in ...Program.cs:line 22

Checking to end recursion. Every recursive method sequence must be terminated based on some condition. Often the first part of the recursive method will have a branch that tests for a condition being met. In this way, the recursive methods can continue until the result is attained. The primitive example here continues until it sums up a value of 10 by incrementing an integer.

Ref parameters. The ref parameter declaration is useful when dealing with recursive methods. This is a way you can have the recursive method return more than one value without using any allocations on the managed heap. You may want to use the count parameter to make sure you don't enter an infinite recursion series.

Six call stack frames. The part of the example text that shows the call stack has six method stack frames with the Recursive method signature in them. The top frame is the exact line where the exception was thrown. The next five frames show the intermediate method calls, which exited at a later point in the method than the top stack frame. If you see the same method signature repeated many times in the call stack, you have a recursive method.

Recursion in compilers

The concept of recursion is used extensively in compiler technologies. In other words, the C# compiler logically uses recursion to parse and compile every C# program you write. Some interesting examples of compiler technologies that use recursion include the type inference algorithms that determine the best fit for method overloading based on method signatures.

Note: These algorithms can be represented using an iterative algorithm that is recursive only in a logical sense.

Recursion versus stacks

Recursion and recursive methods can be changed to use a stack-type structure instead of true recursion. This exchanges method call frames for object instances on the managed heap in the C# language. Navigating a Stack collection in the Visual Studio debugger is much easier than a call stack that is very deep, and this is a good reason to prefer a Stack-based collection over a true recursive method.

Uses

Recursive methods and approaches are widely used in compiler technologies, and also for algorithms that solve puzzles that are either real-world puzzles or game-oriented. Recursion allows you to implement a brute-force search of all possibilities and all possibilities after that. Recursion can be used to implement certain forms of contrived artificial intelligence.

In The Art of Computer Programming, Donald Knuth discusses recursion at depth and uses examples of combinatorics. Algorithms that search for anagrams can be implemented with recursive algorithms.

Summary

We looked at recursive methods in the C# language. You can call a method inside its own body and use reference variable parameters in the signature. We also saw the call stack for a recursive algorithm that encountered an error after several levels of recursion. And finally we noted related issues to recursion and its applications in the field of computer programming and computer science.