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.

They ask, “What’s the point? Why bother learning about recursion?”

This article will answer these questions, with important real-world cases where recursion is more readable, more efficient, and works better than iteration.

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

1
2
3
4
5
6
    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.

28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    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[0], out num1))
                return double.NaN; // Error exit

        String op1 = "";
        if (numTerms >= 2)
            op1 = terms[1];

        double num2 = 0;
        if (numTerms >= 3)
            if (!double.TryParse(terms[2], 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.

53
54
55
56
57
58
59
        // 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.

60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
        // 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.

82
83
84
85
86
87
88
89
90
91
92
93
94
95
    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.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
    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

Exercise for the Reader

Wouldn’t parentheses and functions also be nice?

Some hints for adding them:

  • 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.