SML 中的斐波那契数列

Question

  1 fun fib 0 = 0                                                                   
  2     | fib 1 = 1                                                                 
  3     | fib n = (fib n-1) + (fib n-2)                                             
  4                                                                                 
  5 val x = fib 8

斐波那契数列中第 n 个数的这种实现有什么不正确的地方？当我运行程序挂起时...

Answer 1

fib n - 1 等同于 (fib n) - 1，而不是 fib (n - 1)。所以行 fib n = (fib n - 1) + (fib n - 2) 再次调用 fib n，导致无限递归。

要解决此问题，请添加括号。

SML 中的斐波那契数列

Fibonacci sequence in SML

sml