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. `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 `ref`It calls itself again based on an incremented value of the parameter it receives. The program also has a commented-out exception.`This demonstrates the appearance of the method call stack frames in a recursive algorithm.`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. `In this way, the recursive methods continue until the result is attained (or the algorithm fails).`The primitive example here continues until it sums up a value of 10 by incrementing an integer.`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. `You may want to use the count parameter to make sure you don't enter an infinite recursion series.`Notes, call stack.` 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. `Then: `The next five show the intermediate method calls—these exited at a later point.`So: `If you see the same method signature repeated many times in the call stack, you have a recursive method.`Activation Record `activation-record`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 `stackoverflowexception`The exception here is a good thing, as it stops a process that would otherwise continue infinitely, wasting time and resources.`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.`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 `overload`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. `This is a good reason to prefer a Stack-based collection over a true recursive method.`Stack `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 `constraint`Maze `maze`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 `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.

FGH GPGOGSGDG; { FGAGsHRecursiveH(GsGd, ref Gscount) F{ FFcount++; FFGrGd >= 10) FF{HG'G{throw GwG)("End");G'HGJ Gd; FF} FFGJ HRecursiveH(GdGy1, ref count); F} FG$F{H FF// FFG{Call recursive mG[ with two parameters. FF// FFHGscountGz0; FFGstotalGzHRecursiveH(5, ref count);H FF// FFG{Gh the GI from the mG[ callsGRalso the call count. FF// FFHG%total); FFG%count); F} } H 10FFF Total Gd of 10 was added up. 6FFF Six mG[ calls. HG) thrown when throw uncommented:H Unhandled G): GO.G): End at G;.Recursive(Int32 Gd, Int32& count) ...G;.cs:line 10 at G;.Recursive(Int32 Gd, Int32& count) ...G;.cs:line 13 at G;.Recursive(Int32 Gd, Int32& count) ...G;.cs:line 13 at G;.Recursive(Int32 Gd, Int32& count) ...G;.cs:line 13 at G;.Recursive(Int32 Gd, Int32& count) ...G;.cs:line 13 at G;.Recursive(Int32 Gd, Int32& count) ...G;.cs:line 13 at G;.Gv()Gk...G;.cs:line 22H GDG; { FGAGfHGvH() F{H FFG{Do not run this program. FFHGvH(); F} } H Process is terminated dueGlStackOverflowG).H GDG; { FGAGfHRecurseH(Gsremaining) F{H FFG{This mG[ could be optimized with tail recursion. FFHGrremaining <= 0) FF{G'GJ; FF} FFHRecurseH(remaining - 1); F} FG$F{H FFG{AttemptGlcall this mG[. FFHRecurseH(1000000); F} } H Process is terminated dueGlStackOverflowG).H

`recursive method=causes StackOverflowException8tests for tail recursion