C# Recursion Optimization

Improve the performance of recursion. Use an optimization to inline recursive calls.

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 Optimization

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.

Tip: One option is still available. We can take the method body from the recursive method X and paste it into the Main method.

Info: Obviously, we cannot force the compiler to completely inline a recursive method.

Here: 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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Recursion Optimization

Related Links:

.Net

Java

Related Links