Sunday, December 7, 2008

Mutual Recursion in F#

Mutual recursion is an important concept in functional programming. It is useful if two function need to call each other. In the following example, I am calculating Fibonacci numbers in straight and mutual recursive fashion:
#light
// Straight Version
let rec fibonacci(n) =
if n<1>=0 "))
if n <=2 then 1 else fibonacci(n-1)+fibonacci(n-2)

let n=fibonacci(8)
printfn "%d" n

// mutual recursion version
let rec f(n)= if n=1 then 1 else g(n-1)
and g(n)= if n=1 then 0 else g(n-1)+f(n-1)

let mr_fibonacci(n)=f(n)+g(n)

let mr_d=mr_fibonacci(8)
printfn "%d" mr_d