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.

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.