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

Question

这是Elm语法页面上的Fibonacci代码.好奇的是递归需要记忆还是懒惰的评估会照顾它？

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

在其他语言(例如Python)中,函数调用的数量将呈指数级增长,n因此if f(30)将计算f(10)为4000次或某些.

• Haskell 这个斐波那契函数如何记忆？

• Python 什么是memoization以及如何在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没有自动记忆,因为函数调用不能保证是确定性的.如果您需要备忘录,则必须自己动手.