scala 函数编程：递归循环输出斐波那契数列

cczfrluj 于 8个月前发布在 Scala

关注(0)|答案(3)|浏览(68)

使用scala学习函数式编程。偶然发现了这个练习。
写一个递归函数来得到第n个斐波那契数（http://mng.bz/C29s）。斐波那契数列的前两个数字是0和1。第n个数字总是前两个数字的和--序列从0，1，1，2，3，5开始。你的定义应该使用局部尾递归函数。

def fib(n: Int): Int

我的答案计算n+1个值并返回第n个。谁能给我一个更好的实现，其中额外的第n+1个值不计算？

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

如果有人感兴趣的话，这是Chiusano和Bjarnason写的《Scala中的函数式编程》一书。练习2.1期待答复。

scala

来源：https://stackoverflow.com/questions/28492880/functional-programming-recursive-loop-output-fibonacci-sequence-in-scala

3条答案

按热度按时间

j8ag8udp1#

我认为：

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

或者使用ByName参数：

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

赞(0）回复(0）举报 8个月前

prdp8dxp2#

我喜欢用stream来实现它。因为代码更短，更容易理解。

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)

获取nth很简单，可以调用fibo.drop(n-1)(0)

赞(0）回复(0）举报 8个月前

omhiaaxx3#

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

  println(fib2(8))

赞(0）回复(0）举报 8个月前

我来回答

scala 函数编程：递归循环输出斐波那契数列

3条答案

相关问题

热门标签

最新问答