Home > Programming > Fibonacci Tree Recursion in Scala

Fibonacci Tree Recursion in Scala

My very first example of a recursion was finding a factorial recursively. The more advanced example of a recursive function was the Fibonacci sequence/series. It goes like this:

F(0) = 1

F(1) = 1

F(n) = F(n-1) + F(n-2)

In Scala it would look like this:

def fib(n:Int) : Int = if ( n <= 0 ) 1 else fib(n-1) + fib(n-2)

Although the above Scala code is simple to write and understand it takes exponential time to run it. A better way would be to optimize it by writing it in a linear time by knowing that fib(n-1) includes fib(n-2) i.e. fib(n-1) = fib(n-3) + fib(n-2). Here is a figure showing how we can change it to run linearly by calling fib(i) only once.

Recursive Linear Fibonacci

Now to convert the above figure into a Scala code:

def fib2(n:Int): (Int, Int) = {
 if ( n <= 1 )
  (1, 1)
  val (x, y) = fib2(n - 1)
  (x + y, x)
def fib(n:Int) = fib2(n)._1
Even though the above version has been optimized from Exponential to Linear time we always have the risk of getting Stack Overflow exceptions. A Tail Recursive algorithm would now become handy to avoid a Stack Overflow exception. Here is how we would write a Tail Recursive Fibonacci.
def fib3(n:Int, a:Int, b:Int) : Int = {
 if ( n == 0 )
  fib3( n - 1, b, a + b )
def fib(n: Int): Int = fib3(n, 0, 1)
A Tail recursive algorithm takes the advantage of an accumulator variable ( a and b  in this case ) to store intermediate values. A Tail recursive algorithm is similar to an iterative approach i.e. any tail recursive algorithm could be written as an iterative algorithm.
  1. No comments yet.
  1. No trackbacks yet.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: