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

简单的来说,当一个问题的可列解中无法由已知的第0步结果及第n步的结果直接计算出第n+1步的解，都不是非递归解.
从复杂度来讲,真正的非递归是指运算时所需要的空间是常数，即所需空间与问题的输入规模无关.
从算法来讲，凡是需要用到数组,树,堆栈来模拟递归的程序都不是非递归程序.

一般的,非递归解得转换都有固定的形式，每一种形式对求解函数都有特殊的要求。比如Cooper变换，要求求解的函数必须构成一个幺半群.反演变换，要求求解的函数必须有反函数.

从概念上来将，可能确实如Trustno1所说，以上的实现方法不能算作非递归解，因为没有同时降低空间和时间复杂度。

如果先不考虑概念问题，把所有递归程序当做一个整体，试图将递归转换成能在不支持递归的语言上的实现，或者单方面降低空间或时间复杂度而言，最优的形式到底有没有？如果有，会是怎么样的？

这个问题真有些难度。上面的模拟堆栈的方法在空间上面的浪费一直让人困扰！

可以采用一个长度为100的定长数组。为了节省 x < 100 情况下的空间，可以采用一个长度 <= 100 的变长队列结构。总体空间应该不会超过 100。
不过，这样一来，在x <= 100的情况下，空间效率和{参数值->返回值}的Values Hash Map的空间效率差不了多少。


对。我只考虑了最简单的情况，很多情况是无法用数学归纳法的。比如很多逼近算法。



T1的意思是，非原始递归递归是无法转化为循环形式的?
还是说，非原始递可以归转化为循环形式，但只是循环形式，实际上没有非递归解，实质上还是递归。Right?

T1给出的这个递归函数
f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1)) .

就是非原始递归？



楼主给的例子，所需要的空间都是常数，3 或者 100。应该是有递归解的。Right ?
用到定长数组（或者有限长度队列），应该可以算非递归程序吧。这和常数空间不矛盾。Right ?



楼主的第一篇文章好像给出了答案。分析执行树，找出可能的公用子节点，就可以优化了。Right?
在一些支持Continuation或者Lazy的语言中，这种公用子节点应该是自动分析优化的。有这样的情况吗？

这和数学归纳法没有什么关系.凡是可计算的函数其势都是可列集，凡是不可计算的函数其势都是连续统.
只要是可列集，就可以使用数学归纳法.




这是因为，他求解的问题都是原始递归函数或者说都是可以化简为原始递归函数的全递归函数.
如果是非原始递归函数，他不可能找到空间复杂度为常数的算法.
上面这个例子,他就根本找不到空间复杂度为常数的算法.当m=4,n=1的时候,已经超出了int的取值范围.




你还是没有明白我的意思,如果一个递归函数可以找到非递归解那么就可以降低复杂度，但是不是所有的递归函数都可以找到非递归解.

针对特定的递归程序，通过分析然后优化并不难。但是有通用的优化方法吗？




所用的例子虽是如此，但我通篇都是针对所有递归来讨论的，试图找出通用的转换模板。

没有

原来Trustno1是搞数学的啊，怪不得数学理论如此深厚。可列集，连续统？听都没听过，见笑了！

请教：如果仅针对原始递归函数而言，转换为非递归实现，空间和时间上达到最优，有没有通用的方法？

原始递归函数的复杂度本身就是最优的.
所有可转化为的原始递归函数都可以转化为尾递归,现在绝大多数的编译器都可以把尾递归的函数堆栈优化掉.

全递归函数是否满足 Cooper变换的要求？
原始递归函数是否满足 Cooper变换的要求？

Cooper变换应该满足楼主的需求。Right ?

原始递归函数和非原始递归函，全递归函数，是递归函数的子集.
Cooper变换只是程序等价变换的一种,这些变换只是将原始递归函数的非原始递归形式变换为原始递归.但是它们所针对的函数都必须要有特定要求.不存在通用的变换方法.