Overview

I remember learning recursion in school. It was one of the most mind warping concepts for me at the time. It wouldn’t be until many years later that the perfect metaphor for me would arrive in the form of the movie Inception. Recursive functions are functions that call themselves as part of their execution. The most common example is the Fibonacci sequence. The Fibonacci sequence is defined as:

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), for N > 1.

This problem is typically introduced to students during a unit on recursion:

Define a function fib(x) which returns the xth number in the sequence.

And here is a quick solution for the problem using recursion.

using System;

namespace fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(GetFibonacciValue(10));
        }

        static private int GetFibonacciValue(int n)
        {
            if(n<0)
            {
                throw new ArgumentException("Argument must be 0 or greater", nameof(n));
            }
            switch(n)
            {
                case 0:
                    return 0;
                case 1:
                    return 1;
                default:
                    return GetFibonacciValue(n-1) + GetFibonacciValue(n-2);
            }
        }
    }
}

Recursion algorithms consist of two elements:

• one or more base cases that are calculated based on the input and nothing else
• one or more inductive cases that are calculated by induction, that is it requires a calculation of a previous value from the algorithm (eventually ending in the base case)

Looking at the fibonacci algorithm: the base case is 0 or 1; the inductive case is all other positive numbers.

Lifting the Curtain

So what’s going on with recursion? How does it work behind the scenes? Most modern languages use a special structure called a “call stack” to manage control flow (what function is being called, what are its parameters where should execution continue after the function returns). When your recursive function calls itself, another frame is placed on the stack as it’s being executed. When you forget to put a base case (or if your function calls itself too many times), you get a Stack Overflow.

Explicit Stack

Sometimes because of memory constraints, you need to make an iterative version of a recursive algorithm. One strategy is to make the stack explicit. The runtime stack has a fixed size. On Windows it’s 1MB for 32-bit and 4MB for 64-bit processes…you can explicitly override it but it’s not recommended. On to the important stuff. Let’s say whatever the reason, you don’t want to use recursion. Making the stack explicit is an option. Let’s see what that looks like.

static private int GetStackBasedFibonacciValue(int n)
{
    var returnValue = 0;
    var stack = new Stack<int>();
    stack.Push(n);
    while(stack.Count>0)
    {
	var frame = stack.Pop();
	switch(frame)
	{
	    case 0:
		break;
	    case 1:
		returnValue++;
		break;
	    default:
		stack.Push(frame-1);
		stack.Push(frame-2);
		break;
	}
    }

    return returnValue;
}

If you look at both versions of the function side by side, You’ll recognize that there is a lot of symmetry. In the stack-based version, we have two stack.Push calls with frame-1 and frame-2 as the values. This looks like the inductive case in the recursive function. The base case are the same as well with case 0 adding nothing to the tally and case 1 adding 1.

Advanced Hacks

With the C# yield keyword, you can generate sequences with less logic. The compiler does most of the heavy lifting for you and the algorithm becomes much easier to follow.

static private int GetEnumeratorFibonacciValue(int n)
{
    return FibonacciEnumerator().Skip(n).First();
}

static private IEnumerable<int> FibonacciEnumerator()
{
    var x = 0;
    var y = 1;
    yield return x;
    yield return y;
    while(true)
    {
	var newValue = x+y;
	yield return newValue;
	x = y;
	y = newValue;
    }

}

Wrapping It Up

So we looked in depth at recursive functions, what happens behind the scenes when you make a recursive call, and how you could make that compiler magic more explicit. Finally we looked at another approach to making recursive functions iterative by using the yield keyword. By the way, this capability is not exclusive to C#. Python supports the yield keyword as well in a construct they call generators. I’m sure if you look, other C-based languages will have a similar feature.

The Full Gist

Here is the full source for the sample.