Coming from imperative paradigm, I have to admin I rarely use recursion in my code design. Because it is very natural way to use loop or to encapsulate the business logic in "Iterator" (even one of the patterns from GOF).
But in functional language, like F#, it is very natural to design application using recursion, which make the code more concise, succinct and expressive. It tells “What”, instead of “How”.
Let’s take a simple Factorial function as an example to explain how recursion works.
let rec factorial n = if n = 0 then 1 else n * factorial (n -1)
The function looks simple, which is exactly the same way as its mathematical expression.
But if we provide a very large number such as 1,000,000, it might raise StackOverFlow exception, because the compiler use stack to store the functions. The stack space is very precious, only 1 M. It sounds like the recursion is not applicable for processing large data. Fortunately, F# compiler can optimize recursion by applying “Tail Recursion”.
“Tail Recursion” is a special recursive function which does not including any other execution after the recursive call, meaning there is no “pending operation”
Obviously, the factorial function above is not “Tail Recursion” because it has to multiply n. How do we solve it? A common approach is to use accumulator pattern. Here is the code:
let rec factorialTR n a = if n = 0 then a else factorialTR (n - 1) (n * a)
The idea is, instead of accumulating the functions in the stack, the code use a “accumulator” type to get the temporal value, which is (n * a) in the function. When it function reaches its base, it only needs to return the “accumulator” value. You see, in this case, compiler does not need to store additional additional functions in the stack any more. Makes sense, right?
Is Factorial function too simple? OK, let’s take some “real world” samples.
1. Sum a List (Just be aware the the list in F# is linked list)
let tempList = [1 .. 1000000] // Non Tail Recursion Version let rec sumList lst = match lst with | [] -> 0 | hd :: tl -> hd + sumList tl sumList tempList // Tail recursion version let sumListTR list = let rec innerSum list total = match list with | [] -> 0 // initial value | hd :: tl -> let ntotal = hd + total innerSum tl ntotal // don't need to store in stack innerSum list 0
The first one is not “Tail Recursion” because the recursion function is not the “last” thing, it has to append the value with hd.
The second one is “Tail Recursion” since it calculates the “AsOf” value and the temporal value is one of the parameter passed in the function. There is nothing needed to be stored in the stack.
2. Map function (Note: Map is one of high order functions common in Functional Language)
// Non-Tail Recursive version map function let rec map f list = match list with | [] -> [] | hd :: tl -> (f hd) :: (map f tl)
// Tail Recursion Version
let mapTR f list = let rec loop f list acc = match list with | [] -> acc | hd :: tl -> loop f tl (f hd :: acc)
loop f (List.rev list) []
“Tail Recursion” makes it a very useful in our tool box. But it might reach its own limitation that “Tail Recursion” is allow one recursion call in a function. If there have more, we cannot covert it to “Tail Recursion”, so we cannot take the optimization offered by F# compiler.
Take a sample when we process a Tree:
type Tree<'a> = | Node of 'a * Tree<'a> * Tree<'a> | Leaf of 'a // Non Trail Recursion version let rec treeSize = function | Leaf _ -> 1 | Node(_, left, right) -> treeSize left + treeSize right // Trail Recursion version let treeSizeTR tree = let rec size_acc tree acc = match tree with | Leaf _ -> 1 + acc | Node(_, left, right) -> let acc = size_acc left acc // Non Tail Recursion on left size_acc right acc // Tail Recursion on right size_acc tree 0
You can see we provide two version of codes to process a tree. The first one is a normal approach by calling two recursive functions. It is interesting to see the second one. As you can see we only have one “Tail Recursion” when processing right side tree. So the whole solution still cannot be optimized by F# compiler. Now what we should do?
Let’s think about how we apply “accumulator” pattern to solve “Trail Recursion” issue again. We pass a temporal value as an argument to the function. Just be ware, in functional language like F#, function is value too. It can be passed and returned! It is a fundamental in functional programming, but it can help us to solve very tricky issue. OK, let me tell you the answer first, then explain.
The answer is to applying continuous passing style (CPS) by passing another function as the “remaining” of the recursive function call. So what does it mean? Still confused? Well, actually it is really confusing. It is not very easy to understand when you see it first time. Still, let’s use Fibonacci function we used in the early to illustrate how continuations works.
let fibonacciCPS n = let rec fibonacci_cont a cont = if a <= 2 then cont 1 else fibonacci_cont (a - 2) (fun x -> fibonacci_cont (a - 1) (fun y -> cont(x + y))) fibonacci_cont n (fun x -> x)
This implementation takes a inner recursive function by passing the number and a continuation function. Actually the continuation function is a closure function.
1. when a <=2, it returns by applying the identifier function (fun x –> x)
2. When a > 2, it recursively calls to reach its base case by calling fibonacci_cont (a – 2), and in the same time, it builds up the closure functions. x is the result of fibonacci_cont (a – 2), and y is the result of fibonacci_cont (a –1). The add x and y.
3. Just be aware we use closure here, which use heap, instead of stack.
It really makes the logic inside out. It does not seem a very natural way when we design the code. It made my head hurt when first seeing this code. But later, I think it is very smart to pass closure function like that. It is really the beautiful side of functional programming.
Well, this blog might be too length. I will continue discussing recursive function later. Now let me finish this blog by putting the code to process a tress using continuation at the end.
let treeSizeCont tree = let rec size_acc tree acc cont = match tree with | Leaf _ -> cont (1 + acc) | Node(_, left, right) -> size_acc left acc (fun left_size -> size_acc right left_size cont) size_acc tree 0 (fun x -> x)
