递归计算向非递归计算转换模板 -- 续

另外 楼主的这个模板有个地方让我很震惊
Java的函数调用栈居然比链表栈还慢？

1.递归调用栈溢出比out of memory容易发生得多，这个在实际计算中常常发生。比如帖子中最后一个例子，用递归缓存结果的方法，递归因子上5000就有可能溢出，仅这一点就可以将递归实现排除。转换后的模型依赖内存大小，一般的PC机上x=50万都可以：

public static double recursion2(double x, Map<Double, Double> values) {
    if (values.get(x) != null) {
      return values.get(x);
    }
    if (x < 3) {
      values.put(x, 10.0);
      return 10.0;
    }

    double f1 = recursion2(x - 1, values);
    double f2 = recursion2(x - 3, values);
    double f3 = recursion2(x - 2, values);
    double result = (f1 + f2 + x) / f3;
    values.put(x, result);
    return result;
  }

2.非递归形式语言独立，而且是一个代码块，可以嵌入至任何计算过程中，这个可能只能算项目的特殊需求吧
3.这个转换模型复杂吗？可能是帖子标题有点唬人，这并不是什么数学理论的论证，只是我花了约一天时间总结出来的规律。各位讨论时列举的情况可是比这个深广得多，复杂得多，令人大开眼界啊




你这只能算是针对特定递归的转化。如果是针对某个特定的递归，优化方法很多，能找到非常优越的方案。但是如果在转换之前，你连递归的形式都不知道，怎么能得出递推公式进而写出for循环呢？举个简单的例子，如果结束条件是f(x) = 1 (x < end)，end是一个调用递归时才能求出的值，你如何确定递推的前几个因子？退一步讲，就算是end是一个明确的值，由于递归形式没有确定，递推的前几个因子也不容易求出。前面buaawhl给出的用move方法来实现的方案就是一例。



你没有仔细的看帖子，上面非递归比递归快，是因为非递归缓存了计算值，而直接的递归重复了许多不必要的计算，导致速度慢，并不是什么Java的函数调用栈比链表栈慢。

哦 我没认真看......
这难道就是传说中的备忘录 那好像你不是第一个哦......
而且你干嘛把递归展开到Java栈上再用备忘录？

晕 才看明白 原来有个这个东西......
new HashMap<Double, Double>

那样的话 你可以把HashMap放到类成员级 递归的时候先检查是否在HashMap中  然后return之前把值存进HashMap里面 应该比你这样展开快得多

跟着起了半天哄 才发现就是备忘录加速的......不过如果楼主纯粹是自己想出来的 也挺不错
不玩了 回去罚站......

如果end的值依赖于f的参数以外的变量（unbound），那就不能缓存f(x)的结果，因为f(x)不是幂等的，多次求值会因为end的不同而得到不同的结果
另外如果f除了求值还有side effect，例如修改一个图的结点，那一般也不是幂等的，也不能缓存

对于某个幂等的递归计算，如果要充分优化时间和空间的效率，最好还是深入研究这个递归，变成递推
例如楼主的f(x) = f(x-1)+f(x-3) if x >= 3, = 10 if x < 3
其实只要缓存3个值，再用一个for就可以递推出来了，因为f(x-4)、f(x-5)等等值都可以丢弃
无论x多大，内存占用都是固定的，而使用一般的缓存方法，x很大时，缓存也会out of memory

实际应用中，如果栈足够用（可以把栈设置得很大），那直接在函数中判断并缓存值就可以省去重复计算了
同样是缓存，但cpu的栈操作还是比自己实现的栈更快，而且代码更简单

如果栈即使设置很大还是不够用，才需要自己在堆上实现栈
而这种规模的计算，往往内存也不够容纳整个缓存，最后还是需要时间、空间一起优化，
就像上面说的只缓存3个值然后递推

有些时候
使用递归是因为他们更适合人类的思维方式

不使用递归更像是机器的方式

编译器或解释器来做这个翻译工作