While imperative programming language paradigm depends on updating mutable variables (or introducing side effect) to change state of the program, pure functional programming only uses immutable data structures to represent their state. Side effect is required if you need your program to do any work (i.e., I/O), but undesirable side-effects are the root of many bugs. Immutability makes you write safer code as the code is more predictable.
When people (most of us!) with imperative programming languages background start looking at functional programming, we probably think that if we aren’t allowed to change anything, how we can even do anything useful at all. The answer is that instead of writing program as a sequence of statements that change the state like we do in imperative style programming, we write functional programs differently.
Today, we are going to look at recursion which is a technique that allows functional programs to implement loop-like algorithm without using mutable variables. Basically, a recursive function is a function that calls itself.
Let’s see implementations of factorial function using loop and recursion in C#:
// using recursion
int Factorial(int n)
{
return n<=1?1:n*Factorial(n - 1);
}
// using loop
int FactorialLoop(int n)
{
var ret = 1;
while (n >= 1)
{
ret *= n--;
}
return ret;
}
Now let’s see our F# implemetations:
let rec factorial x =
if x <= 1 then
1
else
x * factorial (x - 1)
let factorialLoop x =
let mutable n = x
let mutable ret = 1
while n >= 1 do
ret <- ret * n
n <- (n - 1)
ret
In C#, the recursive and non-recursive function signature are the same. However, in F#, the rec keyword is needed by the F# type inference system. (I show F# implementation in loop just to show that we can also write F# code in imperative style by using mutable keyword as well although it’s not preferable.)
NOTE: Writing the recursive functions like this every time we need loop-like algorithm can be cumbersome, so most functional languages provide an easier way for doing recursion with higher-order function technique (i.e., Map or Reduce functions). I will write about it in the later post.
Stack Overflow
Ok. Now we can use recursion to implement loop-like algorithm even we aren’t allowed to use mutable variable. However, there is one problem. As you might already know, internally, when a function is called, the caller state will be put into the stack. So if we have a recursive function that call itself deeper and deeper, the program might experience Stack overflow.
Let’s set a break point at the base case and look at our call stack when we call F# factorial 10:
Although we should not have any stack overflow issue here, stack is not infinite resource, the naive recursive function can cause stack overflow with large number of iterations eventually.
Intermediate Language
Before we talk about tail recursion, let’s talk about IL or Intermediate Language.
What is IL or Intermediate Language? When you compile CLI languages like C#, VB, or F#, the .NET compiler generates IL. You can think about it as the native or assembly language of .NET which runs on CLR. When the .NET application is run, each IL method is translated into native machine code Just-In-Time before it’s first executed.
Although it looks just like normal assembly language, IL is a stack-based language and has no concept of registers. As we walk through each samples, we will talk about some of those instructions and learn what it does.
Tail Recursion
Now we understand recursion, stack overflow, and IL, let me introduce tail call and tail recursion. Tail recursion is a special form of recursion, where the compiler can optimize the recursive call in tail position to not allocate stack space to keep caller state. The idea is that if a compiler can guarantee that the call to the recursive function is the tail call or last action that happens before the function returns, there is no need to keep the caller state in the stack at all!
F# is a functional-first language and its compiler is designed to provide tail-call optimization if possible. The most efficient way is to turn the recursive function into a function with a loop. If the compiler can’t do that because the recursive function is more complex, then the compiler generate call IL with a tail. prefix to let the JIT compiler uses the tail call.
Let’s look at the recursive version of the factorial function in F# again:
let rec factorial x =
if x <= 1 then
1
else
x * factorial (x - 1)
At the first glance, we might think that factorial (x-1) is the last action of the function. However, the last action is actually a multiply operation. If you don’t believe me, you can just look at the IL generated from this function.
Don’t worry if you don’t understand most of the IL, what I want you to see is mul, which is a multiply operation, is executed before ret, which return from the function, and after call that is the IL that call the function. In this case, it calls its own function recursively.
If F# code above is not tail-recursive function, then how we can create tail-recursive function. In functional programming we have patterns that we can use to make sure that our recursive function is tail-recursive.
Accumulator Pattern
The first pattern is called Accumulator Pattern. In this pattern, we introduce another parameter, accumulator, that keeps the current state of the recursion, so that information doesn’t need to be kept in the call stack and used later. Let’s see how we can apply the pattern to our factorial function above.
let accFactorial x =
let rec accTailRecursiveFactorial x acc =
if x <= 1 then
acc
else
accTailRecursiveFactorial (x - 1) (acc * x)
accTailRecursiveFactorial x 1
So we basically create a non-recursive function that will get called by the consumer. The non-recursive function has the nested recursive function that accepts two parameters, one is the same recursive parameter, and another one, acc, is a parameter that accumulates multiplied result together. Let’s see the call stack when we execute accFactorial 10.
As you can see, our call stack is pretty clean now!
When F# compiler sees that the last action is a call to a recursive function, it knows that it can generates IL with tail. prefix. When JIT sees the tail. prefix, it knows that it must use a tail call.
(NOTE: some lines have been cut to make the screenshot fit the page)
Continuations
In this pattern (aka continuation passing style), we will see the power of F# and functional programming language! When we treat a function as a value, we can pass it around, make a copy, or create a new one on the fly. So instead of pass another parameter with the accumulated value like in Accumulator Pattern case, why don’t we just build expressions on the fly and pass them via function instead!
Let’s implement the same factorial function with this pattern:
let contFactorial x =
let rec contTailRecursiveFactorial x f =
if x <= 1 then
f()
else
contTailRecursiveFactorial (x - 1) (fun () -> x * f())
contTailRecursiveFactorial x (fun () -> 1)
The implementation looks just like the Accumulator Pattern. In this pattern, we also have an outer function which is non-recursive and the nested recursive function. However, instead of passing an accumulator, we pass a function!
Let’s see the call stack and we should see the clean call stack:
Now let’s see the generated IL and we should see tail. prefix again:
The advantage of using Continuations is that you are not limited to passing a single computed value which might not be possible to do in more complicated recursive function which I can post about it later.
Happy Coding!
Cyan By Fuchsia 