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.

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.

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);
    }
}
10              Total value of 10 was added up.
6               Six method calls.
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.

class Program
{
    static void Main()
    {
        // Do not run this program.
        Main();
    }
}
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.

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);
    }
}
Process is terminated due to StackOverflowException.

Change

This program uses recursion to compute different ways of making change to match a specified amount. Change() will print out all the ways you can make change for a specified amount.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List<int> coins = new List<int>();
        List<int> amounts = new List<int>() { 1, 5, 10, 25, 50 };
        //
        // Compute change for 51 cents.
        //
        Change(coins, amounts, 0, 0, 51);
    }

    static void Change(List<int> coins, List<int> amounts, int highest, int sum, int goal)
    {
        //
        // See if we are done.
        //
        if (sum == goal)
        {
            Display(coins, amounts);
            return;
        }
        //
        // See if we have too much.
        //
        if (sum > goal)
        {
            return;
        }
        //
        // Loop through amounts.
        //
        foreach (int value in amounts)
        {
            //
            // Only add higher or equal amounts.
            //
            if (value >= highest)
            {
                List<int> copy = new List<int>(coins);
                copy.Add(value);
                Change(copy, amounts, value, sum + value, goal);
            }
        }
    }

    static void Display(List<int> coins, List<int> amounts)
    {
        foreach (int amount in amounts)
        {
            int count = coins.Count(value => value == amount);
            Console.WriteLine("{0}: {1}",
                amount,
                count);
        }
        Console.WriteLine();
    }
}
1: 51
5: 0
10: 0
25: 0
50: 0

1: 46
5: 1
10: 0
25: 0
50: 0

1: 41
5: 2
10: 0
25: 0
50: 0

1: 41
5: 0
10: 1
25: 0
50: 0

1: 36
5: 3
10: 0
25: 0
50: 0

Notes, Change method

Change() first tests for the ideal amount, and if this is reached, it prints it to the screen. It tests to make sure the change collected has not exceeded the target.

Output

Display() prints the frequencies of the coins that can be added together to reach the target value. In the example, all of the output will add up to 51 cents.

SICP

The Structure and Interpretation of Computer Programs book uses the "change" example in its first chapter. It counts ways to compute change for 100 cents. See section 1.2.2 Tree Recursion.

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.

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.

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.