CODEWITHSUNDEEP
scalarecursionfunctional-programmingfibonacci
Saman
Saman

Reputation: 541

functional programming: recursive loop output fibonacci sequence in scala

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.

Upvotes: 2

Views: 1439

Answers (3)

user22455919
user22455919

Reputation: 1

def fib2(n:Int):Int={
    if (n<1) 0
    else if (n<=2) 1
    else fib2(n-1) + fib2(n-2)
  }

  println(fib2(8))

Upvotes: 0

user5102379
user5102379

Reputation: 1512

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)
}

Upvotes: 2

fairjm
fairjm

Reputation: 1187

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)

Upvotes: 1

Related Questions