C# Recursion Optimization

Recursion optimization. A method call adds a stack frame.

In a recursive method, the stack frame depth can grow large. A compiler cannot inline all recursive methods. But a programmer can optimize a recursive method by inlining the first call.

Recursion

Example. This example shows a program that calls a recursive method. Technically this call could be subject to tail optimization by a compiler. But this is not the point of the demonstration. Upon execution, the sum of the list elements is 45.

And: The recursive method X will be called 11 times total. On the last call, it does not enter the inner if-statement block.

C# program that uses recursive method

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
	// ... Call recursive method directly.
	List<int> list = new List<int>();
	X(list, 0);

	// ... Verify sum.
	Console.WriteLine(list.Sum());
    }

    static void X(List<int> list, int value)
    {
	if (list.Count < 10)
	{
	    list.Add(value);
	    X(list, value + 1);
	}
    }
}

Output

45

Inline. How could the recursive program be improved? Let's assume there is additional complexity in the method, and we cannot change it to an iterative method. It must use recursion. And let's also assume tail recursion is not applied.

One option is still available. We can take the method body from the recursive method X and paste it into the Main method. Obviously, we cannot force the compiler to completely inline a recursive method.

Tip: This program reduces the calls to the X method by 1. It also reduces the stack depth by 1 frame.

C# program that inlines recursive call

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
	// ... Inline first recursive call.
	List<int> list = new List<int>();
	if (list.Count < 10)
	{
	    list.Add(0);
	    X(list, 0 + 1);
	}

	// ... Verify sum.
	Console.WriteLine(list.Sum());
    }

    static void X(List<int> list, int value)
    {
	if (list.Count < 10)
	{
	    list.Add(value);
	    X(list, value + 1);
	}
    }
}

Output

45

Compilers. Some C++ compilers provide an option to force inlining of a recursive method to a number of levels. Microsoft's C++ compiler allows this. I have memories of requiring 600 megabytes of RAM to compile a small recursive method.

And: This option basically enabled the impossible. It let us inline a recursive method that could not be tail-optimized.

However, the C# compiler has no equivalent option. Using manual approaches, such as the one described here, are an alternative. And often, you can eliminate steps in the first call of a recursive method this way.

Info: Method call depth is relevant to performance. A shallower stack frame is faster.

Method Call Depth Performance

Summary. Recursive methods are not dominant in most programming jobs. But they are an intriguing way to hone one's skills. Plus they can solve many complex problems. If a method takes over the world, it will likely be a recursive one.