swift 中的递归斐波那契函数

Question

我尝试为斐波那契数列编写递归函数。我用一个数组来保存预先计算的元素来改进算法（这是一种常见的做法）。

这是我的代码：

var n = Int(readLine()!)

var arr = [Int](repeating:0, count:n!)
arr[0] = 1
arr[1] = 1
arr[2] = 2


func fib(n : Int, arr: inout [Int]) -> (Int,[Int]){

    if arr[0] != 0 {
        return (arr[n],arr)
    }

    arr[n] = fib(n: n - 1,arr: &arr).0 + fib(n: n - 2,arr: &arr).0
    return (arr[n],arr)
}
n! -= 1
print(fib(n:n! ,arr: &arr).0)

注意：3 < n

任何整数 n 的答案都是 0。

我该如何解决？

我知道使用全局变量更容易（用于保存操作），但我不知道该怎么做。

Answer 1

错误似乎在第一个 if 语句中：

if arr[0] != 0 {
    return (arr[n], arr)
}

如果数组的第一个元素不为0，那么你returnarr[n]。好吧，arr[0] 始终为 1，因此条件始终为真，但是对于所有 n >= 3，arr[n] 最初为 0，这就是导致观察到的行为的原因。

我想你的意思是：

if arr[n] != 0 {

此外，该函数不需要 return 数组，因为您正在使用 inout - 通过引用传递数组。您没有在任何地方使用元组的第二项，是吗？所以函数可以写成：

func fib(n : Int, arr: inout [Int]) -> Int {

    if arr[n] != 0 {
        return arr[n]
    }

    arr[n] = fib(n: n - 1,arr: &arr) + fib(n: n - 2,arr: &arr)
    return arr[n]
}

Answer 2

func fibonacciOf(_ number: Int) -> Int {
    if number == 1 || number == 2 {
        return 1
    }

    return fibonacciOf(number - 2) + fibonacciOf(number - 1)
}

print(fibonacciOf(5))

swift 中的递归斐波那契函数

Recursive Fibonacci function in swift

recursion

function

sequence

fibonacci

swift