functional programming: recursive loop output fibonacci sequence in scala

2
votes

Learning functional programming using scala. Came across this exercise.

Write a recursive function to get the nth Fibonacci number (http://mng.bz/C29s). The first two Fibonacci numbers are 0 and 1. The nth number is always the sum of the previous two—the sequence begins 0, 1, 1, 2, 3, 5. Your definition should use a local tail-recursive function.

def fib(n: Int): Int

My answer computes n+1 values and returns the nth. Can anyone show me a better implementation where the extra n+1th value is not computed?

object patterns {

    def fib(n : Int): Int = {
        @annotation.tailrec
        def go(n: Int, prev2: Int, prev: Int): Int =
            if(n<=0) prev2 
            else go(n-1, prev, prev2+prev)
        go(n, 0, 1)
      }
}

In case anyone is interested, this is from the book functional programming in scala by Chiusano and Bjarnason. Exercise 2.1 Looking forward to the replies.

2
scalarecursionfunctional-programmingfibonacci
If n==0, you must compute one value. How do you propose to lower that figure? – n. 1.8e9-where's-my-share m.

2 Answers

2
votes

I think this:

def fib2(n: Int): Int = {
  if (n < 1) 0
  else if (n < 2) 1
  else {
    @annotation.tailrec
    def go(i: Int, prev2: Int, prev: Int): Int =
      if (i == n) prev
      else go(i + 1, prev, prev2 + prev)
    go(2, 1, 1)
  }
}

or using ByName param:

def fib3(n: Int): Int = {
  @annotation.tailrec
  def go(n: Int, prev2: Int, prev: => Int): Int =
    //                            ^ ByName
    if (n <= 0) prev2
    else {
      val p = prev
      go(n - 1, p, prev2 + p)
    }
  go(n, 0, 1)
}
1
votes

I like to use stream to implement it. Because the code is shorter and easier to understand. 

      def fibo():Stream[Int] = {
        def addRec(o1:Int,o2:Int):Stream[Int] = {
          o1 #:: addRec(o2,o1 + o2)
        }
        addRec(1,1)
      }

      println(fibo().take(100).toList)

get the nth is simple to call fibo.drop(n-1)(0)