我正在使用尾递归对斐波那契数进行编程，它背后的想法似乎与动态编程相同。那么它们是一样的吗？或者更确切地说，它们之间有一些相似之处？如果不是，它们何时变得不同？
问问题
2218 次
3 回答
3
这些术语本身虽然相关，但无论如何都不等同：
动态编程是一种解决问题的方法，可以使用或不使用尾递归来实现。更一般地说，它需要“记忆”。
尾递归是实现动态规划算法的常用方法，因为它专门将记忆逻辑应用于特定领域。
于 2012-09-30T00:29:57.680 回答
1
我明白你为什么要问这个问题。动态规划背后的想法是将问题分解为更小的问题，这与许多递归（尾或非尾）函数背后的想法完全相同。
这实际上是一种苹果与橘子的比较，有很多很好的答案，但有一件事让你意识到为什么很难比较这两个想法：在某些语言中，包括 Java，从技术上讲，你不能使用尾递归. 您可能知道，尾递归函数不会存储其调用的结果堆栈并在以后使用它们。然而，在 Java 中，为每个方法调用维护一个堆栈跟踪。这会使用堆栈空间，如果运行次数过多，可能会出现堆栈溢出。因此，任何看起来可能是尾递归的 Java 方法实际上都不是。
于 2012-09-29T05:12:26.030 回答
0
动态编程通常是一种更有效的方法来完成与尾递归相同的任务。主要区别在于动态编程存储已经计算的结果，因此如果出现相同的操作，而不是再次运行代码，只需查找该值。这会占用更多空间/内存，但会产生更快的算法。
在斐波那契的情况下，动态编程解决方案是不断添加数组中的最后两个元素以获得下一个元素。尾递归解决方案将从头开始计算斐波那契的每个值。
于 2012-09-29T04:46:03.193 回答