在 Swift 中尝试使用自下而上的方法实现斐波那契函数时出现运行时错误？

Question

我正在尝试在 Swift 5 中实现斐波那契函数。当我在 Xcode 游乐场上实现该函数时（我从 CSDojo's youtube video 中获取了该函数的代码），我遇到了这条错误消息

error: Execution was interrupted, reason: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0)

起初我以为错误一定是下标索引超出范围。所以我再次检查了我的代码，似乎没有问题。现在我想知道为什么当我尝试运行 computeFiboBottomUp(n: 100) 时从 Xcode 游乐场收到此错误消息？它工作正常，直到 computeFiboBottomUp(n:35)。

是不是栈上的递归调用太多，编译器处理不了？还是我的代码可能包含错误？

func computeFiboBottomUp(n: Int) -> Int {
    var bottom_up: [Int?] = []
    if bottom_up.isEmpty {
        for _ in 0...n {
            bottom_up.append(nil)
        }
    }
    if n == 1 || n == 2 { return 1 }
    bottom_up[1] = 1
    bottom_up[2] = 1
    for i in 3...n {
        bottom_up[i] = bottom_up[i-1]! + bottom_up[i-2]!
    }
    return bottom_up[n]!
}

computeFiboBottomUp(n: 5)
computeFiboBottomUp(n: 35)
computeFiboBottomUp(n: 100) // error...

Answer 1

您的代码中没有递归。

请注意 Fib(35) 对于整数溢出来说太小了，但是 Fib(100) 对于 32 位和 64 位整数来说肯定太大了，所以你的编译器会捕获整数溢出错误。

您可以为 32 位有符号整数设置限制 n=41，为 64 位有符号整数设置 n=92。

更高的值需要使用 long/arbitrary 精度整数算法。

在 Swift 中尝试使用自下而上的方法实现斐波那契函数时出现运行时错误？

Runtime Error when Trying Bottom Up Approach to Implement Fibonacci function in Swift?

algorithm

fibonacci

bottom-up

swift