这个 Elm Fibonacci 例子需要记忆吗？

Question

这是 Elm 语法页面上的斐波那契代码。只是好奇递归是否需要记忆或惰性评估是否会处理它？

fib n = case n of
  0 -> 1
  1 -> 1
  _ -> fib (n-1) + fib (n-2)

在其他语言中（例如 Python），函数调用的数量在 n 中会呈指数增长，因此在 if f(30) 中会计算 f(10) 大约 4000 次或某事。

Haskell How is this fibonacci-function memoized?
Python What is memoization and how can I use it in Python?

Answer 1

查看编译后的源代码（从 Elm 0.18 开始），您会看到 Elm 代码被转译为以下 javascript 代码（变量名称可能不同）。

var _user$project$Temp1483721371847322$fib = function (n) {
    var _p0 = n;
    switch (_p0) {
        case 0:
            return 1;
        case 1:
            return 1;
        default:
            return _user$project$Temp1483721371847322$fib(n - 1) + _user$project$Temp1483721371847322$fib(n - 2);
    }
};

Javascript 不会自动记忆，因为不能保证函数调用是确定性的。如果您需要记忆，则必须自己动手。

这个 Elm Fibonacci 例子需要记忆吗？

does this Elm Fibonacci example need to be memoized?

memoization

dynamic-programming

elm