使用 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 期待回复。
我认为:
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)
}
我喜欢用
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)
def fib2(n:Int):Int={
if (n<1) 0
else if (n<=2) 1
else fib2(n-1) + fib2(n-2)
}
println(fib2(8))