C# Recursion Example

Show how to develop algorithms based on recursion and review some recursion research.

Recursion. This is a concept. A recursive method calls itself. Recursive methods are used extensively in programming and in compilers.

Recursion, notes. These algorithms help with complex problems. They solve problems and puzzles with brute force. They exhaust all possibilities.

Tip: Recursive algorithms are often used for complex searching and simulation. They add needless complication in other programs.

Example. Here is a recursive method. The method has 2 parameters, including a ref parameter. It checks a condition near the top of its method body, as many recursive algorithms do.Ref

And: It calls itself again based on an incremented value of the parameter it receives. The program also has a commented-out exception.

Tip: This demonstrates the appearance of the method call stack frames in a recursive algorithm.

End: The primitive example here continues until it sums up a value of 10 by incrementing an integer.

Call stack: The call stack has six method stack frames with the Recursive method signature in them.

C# program that uses recursive method 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

StackOverflowException. This may be the shortest valid C# program that will crash. The Main method calls Main. The stack will overflow, leading to a memory error.StackOverflowException

Tip: The exception here is a good thing, as it stops a process that would otherwise continue infinitely, wasting time and resources.

C# program that causes StackOverflowException class Program { static void Main() { // Do not run this program. Main(); } } Output Process is terminated due to StackOverflowException.

Tail recursion. Does the C# compiler optimize tail recursion? Here we show a method called Recurse that could be optimized to iteration using tail recursion.

Result: The compiler does not optimize the tail calls in this program. So it causes a stack overflow.

Thus: The programmer will need to write tail-recursive methods with iteration to achieve optimal performance in C# programs.

C# program that tests for tail recursion class Program { static void Recurse(int remaining) { // This method could be optimized with tail recursion. if (remaining <= 0) { return; } Recurse(remaining - 1); } static void Main() { // Attempt to call this method. Recurse(1000000); } } Output Process is terminated due to StackOverflowException.

Notes, an end. Every recursive method sequence must be terminated. Often the first part of the recursive method will have a branch that tests for a condition being met.

And: In this way, the recursive methods continue until the result is attained (or the algorithm fails).

Notes, ref. The ref keyword is useful when dealing with recursive methods. We have the recursive method return more than one value without using any allocations on the managed heap.

Tip: You may want to use a count parameter to make sure you don't enter an infinite recursion series.

Compilers. The concept of recursion is used in compilers. Every compiler uses some form of recursion. The C# compiler logically uses recursion to parse and compile every program.

Compilers, continued. In compilers, consider the type inference algorithm. This is recursive. This algorithm determines the best fit for method overloading based on method signatures.Overload

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

Stacks. Recursion 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.

And: This is a good reason to prefer a Stack-based collection over a true recursive method.

Stack

Uses. Algorithms that solve puzzles use recursion. We can implement a brute-force search of all possibilities and all possibilities after that.Constraint Puzzle Maze

Tip: Recursion can be used to implement certain forms of artificial intelligence.

Some research. In The Art of Computer Programming, Donald Knuth discusses recursion at depth and uses examples of combinatorics. Anagrams can be implemented with recursive algorithms.Anagram

A summary. There are tricks to using recursive methods. Reference parameters (with the ref and out keywords) are often useful. We examined the call stack for a recursive algorithm.

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 Example

Related Links:

.Net

Java

Related Links