dynamic-programming - 这个 Elm Fibonacci 例子需要记住吗？

Question

这是 Elm 语法页面上的斐波那契代码。只是好奇递归是否需要内存或懒惰评估是否照顾它？

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

在其他语言(例如 Python)中，函数调用的数量会在 n 中呈指数增长。所以如果 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 不会自动内存，因为不能保证函数调用是确定性的。如果您需要内存，则必须自己动手。