The Basic of Recursive Function in F#

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)

 

 

Happy programming!

Advertisements

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