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)
 }
 else
 {
  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 )
  b
 else
  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.
Advertisements
  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 )

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

%d bloggers like this: