斐波那契函数的堆栈溢出

Question

我还在学习F#，所以请对我温柔一点！我试图定义一个函数来生成像这样的斐波那契数...

let rec fib n =
  match n with
  | 0 -> 1
  | 1 -> 1
  | n -> fib(n-1) + (fib n-2)

然而，虽然这给出了 0 和 1 的正确结果，但它给出了 2 的堆栈溢出。我知道这不是尾递归，但是对于 2 的输入，我不希望它是一个问题。

我认为模式匹配的工作方式是向下的，所以输入 2，它会匹配第三个模式，给出 1+1 的结果（是 fib 0 和 fib 1 的结果）。

为什么我会得到 SO？

Answer 1

你的声明：

| n -> fib(n-1) + (fib n-2)

表示：

| n -> fib(n-1) + fib(n)-2

如果我有这样的调用，它会与 fib(n-1) 一起工作，因为每次调用 n 的值都会减少 1，而对于 fib(n) 你会继续调用相同的方法具有相同的值，直到您获得 Whosebug 异常。为避免这种情况，您需要：

| n -> fib(n-1) + fib(n-2)

Stack overflow with Fibonacci function