I absolutely loved reading SICP and listening to the lectures! This UC Berkeley course is proving to be a second wave of enlightenment. Such valuable material, and all free!

Recursion is absolutely ubiquitous as the loop control flow mechanism in a world without assignment. Familiar constructs such as for/while loops make no sense without mutation.

 

Here is a recursive definition of a recursive process for calculating factorial (in Scheme):

 

(define (factorial n)

  (if (<= n 1)

     1

     (* n (factorial (- n 1)))

  )

)

 

My previous post has a nice example of how the “shape” of the process can be seen by way of successive substitutions.

 

This now, is another recursive definition of factorial, but this time defining an iterative process using the common tactic of an accumulator:

 

(define (factorial n a)

  (if (<= n 1)

     a

     (factorial (- n 1) (* n a))

  )

)

 

Comparing these in the “Stepper” in DrScheme makes for a nice example:

 

 

The former builds up deferred multiplications while the latter accumulates the answer directly.

 

So what happens when we try this in C#?

 

using System;

 

public static class Tail {
    public static int Factorial(int n, int a) {
        if (n <= 1) return a;
        return Factorial(n - 1, n * a);
    }

 

    public static void Main() {
        Factorial(7, 1);
    }
}

 

Watching in the debugger, you can see that a call stack is built and then collapsed even though this is clearly tail recursive.

 

 

Looking at the IL for this we can see that it’s doing a regular “call” and “ret” – silly C# compiler!

 

 

Tail recursion can be thought of as a “goto with parameters” and we can manually implement this if we like:

 

public static int Factorial(int n, int a) {
    start:
    if (n <= 1) return a;
    a *= n; n--;
    goto start;
}

 

But how horribly ugly! Using mutation and goto! Notice also that if a *= n; and n--; were reversed it would be a bug. As soon as you introduce assignment, bugs like this are possible.

 

Side note: I enjoy being one of the happy devs who’s moved to managed languages and longer has to worry about stack and heap corruption, memory leaks and buffer overruns. Next I want to move away from the store and branch instructions in our von Neumann machines. We all broke free of goto many years ago but most are still fighting with assignment to this day. Eliminating this whole class of bugs will be great.

 

Another example that comes to mind: Some people find it amazing to hear that in F# you only very, very rarely have any need at all for the concept of null (mainly only for backward compat with .NET libraries). Wouldn't you love to say, "NullRefException? What's that!?”

 

Okay, back to recursion; lets try this again in F# this time:

 

let rec Factorial n a =
    if n <= 1 then
        a
    else
        Factorial (n - 1) (n * a)

Factorial 7 1

 

In the debugger, it’s apparently smart enough to eliminate the call stack! Excellent.

 

 

Let’s look at the IL:

 

 

Sweet, the compiler is doing the “sub”, “mul” and stomping on the original arguments (“starg.s”), then simply branching (“br.s”) back to the beginning. I have no problem with compiler-generated mutation and goto.

 

I’m curious now, if the compiler is smart enough to optimize tail recursion in the form of a function calling itself, what will it do with proper tail calls to other functions? It can’t be branching between functions:

 

let rec Even n =
    n <> 1 && (n = 0 || Odd (n – 1))  

And Odd n =
    n <> 0 && (n = 1 || Even (n – 1))

Even 5

 

Looking in the debugger, we can see that Even 5 calls Odd 4, which calls Even 3, calling Odd 2, which finally calls Even 1 and returns false; all of this without a call stack.

 

 

Nice. But how? As usual, the IL gives it away:

 

 

The “.tail” prefix tells the JIT compiler that stack frame can be recycled before the following “call.” It turns out that even without this prefix, the JIT compiler can potentially be smart enough to optimize. Jomo Fisher has a nice post on this.

---

I just gave a brownbag talk on this. Here's the deck if you're interested.