scala尾递归实现斐波那契数列
时间: 2023-11-20 07:52:25 浏览: 111
在Scala中,可以使用尾递归来实现斐波那契数列。尾递归的实现方式是将递归调用的结果作为参数传递给下一次调用,从而避免了递归调用栈的溢出。下面是一个使用尾递归实现斐波那契数列的示例代码:
```
def fibonacci(n: Int): Int = {
@annotation.tailrec
def loop(n: Int, prev: Int, cur: Int): Int =
if (n == 0) prev
else loop(n - 1, cur, prev + cur)
loop(n, 0, 1)
}
```
在这个实现中,我们使用了一个内部函数`loop`来进行尾递归。`loop`函数接受三个参数:当前的计数器`n`、前一个斐波那契数`prev`和当前的斐波那契数`cur`。在每次递归调用中,我们将`n`减1,将`cur`作为下一次调用的`prev`参数,将`prev + cur`作为下一次调用的`cur`参数。当`n`等于0时,我们返回`prev`作为结果。
需要注意的是,在这个实现中,我们使用了`@annotation.tailrec`注解来确保编译器对`loop`函数进行尾递归优化。如果`loop`函数不是尾递归,编译器会给出一个警告。
相关问题
scala实现斐波那契数列
以下是一种在 Scala 中实现斐波那契数列的方法:
```
def fib(n: Int): Int = {
if (n <= 1) return n
return fib(n-1) + fib(n-2)
}
```
这里使用了递归的方法实现斐波那契数列,如果 `n` 小于等于 1,则直接返回 `n`;否则递归调用 `fib` 函数,求出 `fib(n-1) + fib(n-2)` 的值。
scala斐波那契数列
Scala是一种运行在Java虚拟机上的编程语言,它结合了面向对象编程和函数式编程的特性。斐波那契数列是一个经典的数学问题,定义如下:第一个和第二个数都是1,从第三个数开始,每个数都是前两个数的和。在Scala中,可以使用递归或循环来实现斐波那契数列。
递归实现斐波那契数列的代码如下:
```scala
def fibonacci(n: Int): Int = {
if (n <= 2) 1
else fibonacci(n - 1) + fibonacci(n - 2)
}
val n = 10
val result = fibonacci(n)
println(s"The $n-th Fibonacci number is: $result")
```
循环实现斐波那契数列的代码如下:
```scala
def fibonacci(n: Int): Int = {
var a = 0
var b = 1
var i = 0
while (i < n) {
val temp = a
a = b
b = temp + b
i += 1
}
a
}
val n = 10
val result = fibonacci(n)
println(s"The $n-th Fibonacci number is: $result")
```
阅读全文