### Recursive Programming in C#: Yes, it’s Useful!

By: Tim Schreyer ## “Seriously, will I ever need recursion?”

I saw that question in a discussion group, and I’ve seen many similar questions in other groups.

Most college textbooks explain recursion by showing an n-factorial method as an example.

Unfortunately, n-factorial should use iteration, because iteration is faster and more efficient for this type of problem. This leads students to assume that iteration is ALWAYS the best choice.

Let’s start by defining recursion and recursive programming…

## What is Recursive Programming?

Recursion is the use of a method that calls itself.

Here is the stereotypical n-factorial example, in C#. Notice how decrementing its input variable implies that recursion is just a different kind of iteration. (It’s not.):

 123456 static double nFactorial(double n)     {         if(n<=1) return 1;             return n * nFactorial(n-1);     } #

## Problems with Recursion in C#

When you call a method, the runtime adds that method to its stack. Recursive calls add multiple copies of the same method to the stack, gobbling up resources and increasing execution times.

What can go wrong:

• Infinite loops
• StackOverflow exceptions
• Long execution times

What you can do about it:

• Examine your logic to minimize the recursion depth
• Use tail-recursion
• Tail recursion in C# isn’t supported, even though .NET supports it, so we won’t discuss it in this article. You can learn more here

So why not just use iteration? Why not make recursion illegal and forget about it?

## Real-World Practical Uses for Recursion in C#

Recursion works best on problems that are already naturally recursive. Here are some examples:

• Factors and primes:
• Factoring requires starting-over (sort of) every time a new factor is found
• Trees:
• Trees also require starting over every time you enter a new branch (directories, lists-of-lists, sorting algorithms, XML files, etc.)
• Compilers and Calculators:
• Source code and calculator operations contain blocks that can’t be processed until other blocks have been read. Using recursion is like pushing these blocks onto a stack.
• Games:
• Some games use recursion to attempt several solutions and choose the best one (maze solvers, chess games, Sudoku solvers, etc.).

Let’s look at one of these cases in detail. A calculator program sounds fun, so let’s write a recursive calculator parser.

## Parsing Calculator Operations With Recursive Programming

The ParseCalc() method shown here parses a string of operations and returns the numerical result. The string contains numbers and operators, separated by one or more blank spaces.

### Initialize

The first step is to convert the operation string into an array and grab the first three terms, which should be two numbers and one operator.

 28293031323334353637383940414243444546474849505152 static double ParseCalc(String operation)     {         // INITIALIZATION:         // Convert the operation string into an array         while(operation.Contains(" "))         operation = operation.Replace(" ", " ");         String[] terms = operation.Split(' ');         int numTerms = terms.Length;         // Grab the first three terms, if possible         double num1 = 0;         if (numTerms >= 1)             if (!double.TryParse(terms, out num1))                 return double.NaN; // Error exit         String op1 = "";         if (numTerms >= 2)             op1 = terms;         double num2 = 0;         if (numTerms >= 3)             if (!double.TryParse(terms, out num2))                 return double.NaN; // Error exit #

### Terminate the Recursion!

The second step is to determine if we have reached the end of the recursion. Recursion should stop when the operation string is empty or contains one number.

 53545556575859 // RECURSION TERMINATION:         if (numTerms <= 0)             return 0;         if (numTerms <= 2) // 2 allows for a final operator, interpreted as '='             return num1; #

### Parse

The last section of ParseCalc() executes the first operator on the first two numbers. It then calls itself recursively to process the remaining operations.

The method must preserve the precedence of the add, subtract, multiply, and divide operations.

So it processes addition and subtraction OUTSIDE of the next recursive call. This causes them to execute AFTER the remaining operations.

And it processes multiplication and division INSIDE the next recursive call. This causes them to execute BEFORE the remaining operations.

 60616263646566676869707172737475767778798081 // PARSING:         switch (op1)         {             case "+":                 String nextOp = EverythingElse(terms, 2);                 return num1 + ParseCalc(nextOp);             case "-":                 String nextOp =                     (-1 * num2).ToString() + " " + EverythingElse(terms, 3);                 return num1 + ParseCalc(nextOp);             case "*":                 String nextOp =                     (num1 * num2).ToString() + " " + EverythingElse(terms, 3);                 return ParseCalc(nextOp);             case "/":                 String nextOp =                     (num1 / num2).ToString() + " " + EverythingElse(terms, 3);                 return ParseCalc(nextOp);         }         return double.NaN; // Error exit     } #

### Repeat

The EverythingElse() method puts the remaining terms into a new operation string for the next recursive call.

 8283848586878889909192939495 static String EverythingElse(String[] terms, int startAt)     {         String result = "";         if (startAt < terms.Length)         {             result = terms[startAt];             for (int n = startAt + 1; n < terms.Length; n++)             {                 result += " " + terms[n];             }         }         return result;     } #

### Test

We’ll use this Main() method to test the ParseCalc() method.

 101112131415161718192021222324252627 public static String[] operations =     {         "1 + 1",         "5 + 2 + 7",         "5 - 2 + 7",         "2 * 7 + 7 * 4",         "50 - 3 * 5 + 7",         "5 * 2 + 2 + 100 / 4 + 5"     };     static void Main(string[] args)     {         foreach (String op in operations)         {             Console.WriteLine(op + " = " + ParseCalc(op).ToString());         }     } #

Here are the results:

1 + 1 = 2
5 + 2 + 7 = 14
5 - 2 + 7 = 10
2 * 7 + 7 * 4 = 42
50 - 3 * 5 + 7 = 42
5 * 2 + 2 + 100 / 4 + 5 = 42

Wouldn’t parentheses and functions also be nice?

• When encountering an open-paren, use an iteration loop to find its corresponding close-paren
• Use a parenthesis depth counter to find the correct close-paren
• Use a recursive call to parse everything between the parentheses
• Don’t worry about lower-level parentheses. The recursive call will parse
them
• Insert the parsed value into either num1 or num2
• If an operator wasn’t given, assume op1 should be multiplication
• Want to add functions? Just treat them similarly to parentheses

Recursion makes it easy to write a fully-functional scientific calculator!

## Use Recursion in the Real-World

There are many cases where recursion is more readable and more efficient than other strategies.

So have fun with recursion! It isn’t just a different kind of iteration.