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

ruby的话想缓存函数的话，直接用内置的Memoize不就行了。。

这个函数实际上是X的Y次幂的Z重积分.
一般性的线性规划法优化,根本无济于事.
不过它的单变量反函数也很有趣,f-1(n),随着n的增大f-1(n)会以难以想象的慢速增大，理论上没有上界，但是一般性的整形值n，f-1(n)<=4.如果一个算法的复杂度能降到o(f-1(N))就是一个o(logN)还要优秀的算法了.

思路不错，不过一般情况还是递归结构上更清晰，非递归的情况会是用在一些不支持递归调用的语言中。这样的语言还是极少的。

Ackermann 函数还是用 A 来表示吧, 而且有意思的是, O(A^{-1}(n)) 这个复杂度其实不可能出现的, 这里有个好玩的结论: 任何一个问题, 如果存在 o(log(log(n))) 的算法, 那么必然存在常数时间的算法. 不过倒是有个有名的算法的复杂度是 O(n*A^{-1}(n)), 一直是被拿来当作平摊分析的经典例子的 ...

嗯嗯, 这个讨论串有意思, 考虑也写点东西.

1. 空间：
递归时堆栈容易溢出说明空间利用率上没有得到优化，但是相比之下，如果转换成循环也不能优化空间，又何必多此一举呢？

递归－>使用栈空间，循环->使用堆空间。

有些语言实现可以在堆上分配栈，那递归和循环就没有本质区别了。

2. 时间：
采用cache等效于缓存中间计算结果，优化运行时间。同样，可以采用只cache一个“窗口”来解决cache的空间问题。如以上各位总结，确定这个“窗口”并不容易，而且不能保证这个“窗口”是足够窄的，这时只好限定cache大小，又以时间来换取空间了。

 

不知道你指的有些语言是指哪些语言？在java, c#, PLSQL等语言下，栈的溢出比out of memory经常得多。

 

 

就空间来讲确实没有优化；但是用来cache的空间会优化运行时间。同时优化空间和时间，对于特定的递归有可能，但不可能找到通用的方法。对于用语言自身的递归特性实现的递归而言，运行时间是瓶颈所在。试试例子中的递归实现就知道了：

 

public static double recursion(double x) {   
  if (x < 3)   
    return 10.0;   
  
  double f1 = recursion(x - 1);   
  double f2 = recursion(x - 3);   
  double f3 = recursion(x - 2);   
  return (f1 + f2 + x) / f3;   
}  

 

例如Lua,就是stackless的. Python也有stackless的实现. 原则上,基于虚拟机的语言都可以实现stackless.

所谓栈的溢出,实际上是栈的使用超出了操作系统给你的配额. 可以用ulimit -s来增加这个上限.
大多数操作系统都是实际用到多少stack分配多少,不会按配额预分配stack,因此不会浪费.

对于用语言自身的递归特性实现的递归而言，运行时间是瓶颈所在。试试例子中的递归实现就知道了：

 
Java代码 复制代码

   1. public static double recursion(double x) {     
   2.   if (x < 3)     
   3.     return 10.0;     
   4.     
   5.   double f1 = recursion(x - 1);     
   6.   double f2 = recursion(x - 3);     
   7.   double f3 = recursion(x - 2);     
   8.   return (f1 + f2 + x) / f3;     
   9. }    

public static double recursion(double x) {   
  if (x < 3)   
    return 10.0;   
  
  double f1 = recursion(x - 1);   
  double f2 = recursion(x - 3);   
  double f3 = recursion(x - 2);   
  return (f1 + f2 + x) / f3;   
}  

不经cache优化的话,大部分时间花在重复计算中间结果,当然慢了.以下是ruby的优化实现:

# x < 3: f(x) = 10.0, else: f(x) = (f(x-1) + f(x-3) + x) / f(x-2)

def f(x, cache = {})
  unless cache[x]
    cache[x] = (x < 3 ? 10.0 : (f(x-1, cache) + f(x-3, cache) + x) / f(x-2, cache))
  end
  cache[x]
end

x = 10000.0
puts "f(#{x}) = #{f(x)}"

在我的机器上(老爷机了),ruby1.8.6不到1秒. 如果是ruby 1.9相信会更快.

* 此例子默认的8192 stack不够用,需增加操作系统的stack上限.我用ulimit -s 100000测试通过.




对于所有类型的递归,同时优化时间和空间的通用方法似乎不存在...用cache来优化时间却是一个通用的方法.

不是我打击楼主的想法

这种只含有加法和移位算子的函数已经有数学公式了 连循环都不用 如果CPU的浮点运算器支持幂运算 那么时间复杂度O(1)就可以搞定 就算不支持浮点幂运算 也只是O(log(n))的时间

递归算法更多是用在搜索或者访问树等复杂结构的时候......

嗯，但是也有很多语言，比如当前做应用系统开发的主流语言JAVA和C#上，都没有类似的实现。我的帖子正源自一个JAVA的应用项目，而且是里面非常小的一小块，不可能改用其他语言或嵌入其他语言，那样会越搞越麻烦。




不太明白你想说什么！这只是一个很简单的算法转换问题，怎么扯到CPU上去了。

Sorry Sorry 我扯远了

我的意思是 就好像菲波那契数列 f(n+2)=f(n+1)+f(n)，f(0)=0,f(1)=1可以推导出
f(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5，m^n表示m的n次幂】

你处理的那类递归 组合数学里其实全都有办法化成通项公式的 而更复杂的递归你这个也处理不了吧

还有 有些简单的尾递归编译器会识别出来并且优化

所以你还是在别的地方下下功夫吧

关于CPU嘛 就是说 一个浮点数的n次方这种运算 有些CPU是可以直接算的 有些需要用程序算
不管哪种 都要比递推还快很多