为什么函数式编程语言支持自动记忆而不是命令式语言？

Question

这是我在互联网上随机发现的关于动态编程的一些讲座中读到的一个问题.(我毕业了,我已经知道动态编程的基础了)

在解释为什么需要记忆的部分,即

// psuedo code 
int F[100000] = {0};
int fibonacci(int x){
    if(x <= 1) return x;
    if(F[x]>0) return F[x];
    return F[x] = fibonacci(x-1) + fibonacci(x-2);
}

如果没有使用memoization,那么许多子问题将被重新计算很多次,这使得复杂性非常高.

---

然后在一个页面上,笔记有一个没有答案的问题,这正是我想问的问题.在这里,我使用的是准确的措辞及其显示的示例:

自动记忆:许多函数式编程语言(例如Lisp)都内置了对memoization的支持.

为什么不用命令式语言(例如Java)？

说明提供的LISP示例(它声称它是有效的):

(defun F (n)
    (if
        (<= n 1)
        n
        (+ (F (- n 1)) (F (- n 2)))))

它提供的Java示例(它声称它是指数的)

static int F(int n) {
  if (n <= 1) return n;
  else return F(n-1) + F(n-2);
}

---

在阅读本文之前,我甚至不知道在某些编程语言中内置支持memoization.

笔记中的声明是真的吗？如果是,那么为什么命令式语言不支持呢？

Answer 1

关于"LISP"的说法是非常模糊的,他们甚至不提这 LISP方言或他们的意思执行.我熟悉的LISP方言都没有做自动记忆,但是LISP可以很容易地编写一个包装函数,将任何现有函数转换为memoized函数.

全自动,无条件的记忆将是一种非常危险的做法,并会导致内存不足的错误.在命令式语言中,它会更糟糕,因为返回值通常是可变的,因此不可重复使用.命令式语言通常不支持尾递归优化,进一步降低了memoization的适用性.