Good! F# (May 2009) support tail recursion very well!

What’s the tail recursion?

In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function, the tail call, is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack. (from Wikipedia)

Still don’t understand? OK, let me show you the code.

int f(int n) {
    return f(n + 1);    // it's the last operation.
}

If you run f(0), you will get a StackOverFlowException.

How about F#?

let rec f n = f (n + 1)

The keyword “rec” tell compiler it’s a recursive function.

We use Reflector to see how it looks like as a C# code:

public static a f<a>(int n)
{
    while (true)
    {
        n++;
    }
}

The magic the compiler done is called Tail Call Optimization. (see Adventures in F#–Tail Recursion in Three Languages)

Another case of tail recursion:

type t() =
member x.f1 n = x.f2 (n + 1)
member x.f2 n = x.f1 (n + 1)

This time, when you run t().f1 0, you will get the StackOverFlowException too.

Don’t worry. Just open the F# project properties dialog and the Build tab. Check the “Generate tail calls” on. Then the exception disappeared.

See what’s different of the IL code:

“Generate tail calls” unchecked

.method public instance !!a f1(int32 n) cil managed
{
.maxstack 5
L_0000: nop
L_0001: ldc.i4.s 0x2e
L_0003: call void [mscorlib]System.Console::Write(char)
L_0008: ldarg.0
L_0009: ldarg.1
L_000a: ldc.i4.1
L_000b: add
L_000c: call instance !!0 Program/t::f2(int32)
L_0011: ret
}

“Generate tail calls” checked


.method public instance !!a f1
(int32 n) cil managed
{
.maxstack 5
L_0000: nop
L_0001: ldc.i4.s 0x2e
L_0003: call void [mscorlib]System.Console::Write(char)
L_0008: ldarg.0
L_0009: ldarg.1
L_000a: ldc.i4.1
L_000b: add
L_000c: tail
L_000e: call instance !!0 Program/t::f2(int32)
L_0013: ret
}

One more case:

type t() =
member x.f3 n = x.f3 (n + 1)

No matter you check the “Generate tail calls” or not, the compiler will do the Tail Call Optimization.

The reflector will render it like this:

public a f3<a>(int n)
{
    while (true)
    {
        n++;
        this = this;
    }
}

Scala compile will do the Tail Call Optimization too, but there’s no “tail” in JVM until now. So we need to wait for the Java 7.

Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: