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

mingliangfeng

浏览: 45690 次
性别:
来自: 墨尔本

最近访客更多访客>>

蓝绿色的天空

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Arithmetic

算法 F#Cache Ruby JavaScript

上一篇文章对递归向非递归转换的原理和过程作了介绍，本篇谈谈具体的代码实现。还是考虑上一篇文章中的递归例子：f(x) = f(x-1) + f(x-3), f(x) = 10 (x < 3)。用上文分析出来的规律，其实现如下：

  public static double nonRecursion(double x) {
    double initValue = x;
    final int endFlag = 3; // count of branches plus 1   
    Map<Double, Double> values = new HashMap<Double, Double>();
    StackItem ci = new StackItem(initValue);
    while (ci != null) {
      switch (ci.flag) {
      case 0:
        x = ci.number;
        if (x < 3) { // exit of recursion   
          values.put(x, 10.0);
          ci.flag = endFlag;
        } else {
          ci.flag = ci.flag + 1;
          StackItem sub;
          if (ci.next == null) {
            sub = new StackItem();
            sub.pre = ci;
            ci.next = sub;
          } else {
            sub = ci.next;
          }
          sub.number = x - 1; // branch one   
          if (values.containsKey(sub.number)) {
            sub.flag = endFlag;
          } else {
            sub.flag = 0;
          }
          ci = sub;
        }
        break;
      case 1:
        x = ci.number;
        ci.flag = ci.flag + 1;
        StackItem sub;
        if (ci.next.next == null) {
          sub = new StackItem();
          sub.pre = ci.next;
          ci.next.next = sub;
        } else {
          sub = ci.next.next;
        }
        sub.number = x - 3; // branch two   
        if (values.containsKey(sub.number)) {
          sub.flag = endFlag;
        } else {
          sub.flag = 0;
        }
        ci = sub;
        break;
      case 2: // two sub items are ready, calculating using sub items   
        x = ci.number;
        double f1 = values.get(ci.next.number);
        double f2 = values.get(ci.next.next.number);
        double result = f1 + f2; // recursive body
        values.put(x, result);
        ci.flag = endFlag;
        break;
      case endFlag: // current item is ready, back to previous item           
        ci = ci.pre;
        break;
      }
    }
    return values.get(initValue);
  }

其中本地的Map类型的变量values用来存放递归因子和它对应的计算出来的值。堆栈是用双向链表来实现的，双向链表非常方便向前回溯和向后取得父节点的子节点。双向链表的item类型为StackItem，它除了拥有向前和向后的指针外，还包含当前递归因子的值和状态。其结构如下：

public class StackItem {
  
  public double number;
  
  public int flag;
  
  public StackItem pre = null;
  
  public StackItem next = null;
  
  public StackItem() {
    this(0);
  }
  
  public StackItem(double number) {
    this.number = number;
    this.flag = 0;
  }
  
}

在本机上运行了一下，由于转换后的非递归程序保存了中间递归因子的计算值，它比直接用java语言实现递归在时间上要快不少。递归参数越大时，其优势越明显。

上一篇文章提到要把分析出来的规律总结成一个通用模板，其实从上面的实现代码中可以看出，模板的框架已经浮现出来了。根据递归函数中的递归调用点，可以确定计算完成时的状态值，进而确定循环体中case的个数。其中每个case里面的代码块都具备可以模板化的特点。总体来说，将一个递归函数分解成如下几块，安插至case框架里面即可：

递归调用出口（exit of recursion）：在当前节点状态为0，即初次遍历至该节点时，会检查递归因子的值。如果能直接计算出来，则计算出来并将状态置为完成；否则，状态递增1，开始计算第一个子节点的值；
递归调用点（branch），包括递归因子的收敛公式，根据其在递归体中出现的顺序安插至case代码体中去；
递归体（recursive body），当节点的所有子节点都完成计算后，根据递归体计算当前节点的值。代码的位置位于倒数第二个case中。

根据上面的分解，递归至非递归的转换模板就已经很清晰了，可以轻易的用模板技术，比如velocity或freemarker来实现。

下面再用上面的规律对一个递归函数进行非递归转换，以验证模板的通用性：

递归函数：f(x) = ( f(x-1) + f(x-3) + x) / f(x-2), f(x) = 10 (x < 3)

附上的代码是对以上函数的递归和非递归的java实现：

  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;
  }

  public static double nonRecursion(double x) {
    double initValue = x;
    final int endFlag = 4; // count of branches plus 1
    Map<Double, Double> values = new HashMap<Double, Double>();
    StackItem ci = new StackItem(initValue);
    while (ci != null) {
      switch (ci.flag) {
      case 0:
        x = ci.number;
        if (x < 3) { // exit of recursion
          values.put(x, 10.0);
          ci.flag = endFlag;
        } else {
          ci.flag = ci.flag + 1;
          StackItem sub;
          if (ci.next == null) {
            sub = new StackItem();
            sub.pre = ci;
            ci.next = sub;
          } else {
            sub = ci.next;
          }
          sub.number = x - 1; // branch one
          if (values.containsKey(sub.number)) {
            sub.flag = endFlag;
          } else {
            sub.flag = 0;
          }
          ci = sub;
        }
        break;
      case 1:
        x = ci.number;
        ci.flag = ci.flag + 1;
        StackItem sub1;
        if (ci.next.next == null) {
          sub1 = new StackItem();
          sub1.pre = ci.next;
          ci.next.next = sub1;
        } else {
          sub1 = ci.next.next;
        }
        sub1.number = x - 3; // branch two
        if (values.containsKey(sub1.number)) {
          sub1.flag = endFlag;
        } else {
          sub1.flag = 0;
        }
        ci = sub1;
        break;
      case 2:
        x = ci.number;
        ci.flag = ci.flag + 1;
        StackItem sub2;
        if (ci.next.next.next == null) {
          sub2 = new StackItem();
          sub2.pre = ci.next.next;
          ci.next.next.next = sub2;
        } else {
          sub2 = ci.next.next.next;
        }
        sub2.number = x - 2; // branch three
        if (values.containsKey(sub2.number)) {
          sub2.flag = endFlag;
        } else {
          sub2.flag = 0;
        }
        ci = sub2;
        break;
      case 3: // three sub items are ready, calculating using sub items
        x = ci.number;
        double f1 = values.get(ci.next.number);
        double f2 = values.get(ci.next.next.number);
        double f3 = values.get(ci.next.next.next.number);
        values.put(x, (f1 + f2 + x) / f3); // recursive body
        ci.flag = endFlag;
        break;
      case endFlag: // current item is ready, back to previous item           
        ci = ci.pre;
        break;
      }
    }
    return values.get(initValue);
  }

分享到：

JavaEye的Bug? | 递归计算向非递归计算转换模板

2008-06-07 23:04
浏览 3983
评论(57)
论坛回复 / 浏览 (55 / 27495)
分类:编程语言
查看更多

57 楼 kimmking 2008-08-21

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

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

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

56 楼 javaeyebird 2008-08-14

mingliangfeng 写道

举个简单的例子，如果结束条件是f(x) = 1 (x < end)，end是一个调用递归时才能求出的值，你如何确定递推的前几个因子？退一步讲，就算是end是一个明确的值，由于递归形式没有确定，递推的前几个因子也不容易求出。

如果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个值然后递推

55 楼 csf177 2008-06-25

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

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

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

54 楼 csf177 2008-06-25

mingliangfeng 写道

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

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

53 楼 mingliangfeng 2008-06-24

引用

一个问题是。
如果楼主只是为了提高时间效率，只需要用查表法(结果缓存)本身就够了。
反正都是缓存结果，递归形式和非递归形式的时间效率和空间效率是一样的。
为什么还需要用那个复杂的模型转换呢？

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[0]=XXX;f[1]=XXX;f[3]=XXX;
for(x=3;x<n;x++)
{
f[x]=(f[x/4-1]+f[x/6-2])/f[x-2];
}

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

引用

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

52 楼 csf177 2008-06-24

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

51 楼 csf177 2008-06-24

mingliangfeng 写道

引用

剩下楼主这个模板适用的也就剩下尾递归了。而在算法比较熟练的人手里尾递归几乎不可能出现(要是能写出递推公式来，有多少人傻到直接翻成递归去算)，且不少编译器能识别并转换尾递归所以说这有多大意义？

不仅仅是尾部递归吧？比如说如下递归:
f(x)=(f(x/4-1) + f(x/6-2))/f(x-2)
这个可比尾部递归复杂多了，但是能通过上面的模板进行转换。不过我不知道这属于哪一类递归，其实我也不知道该怎样给递归公式分类。

这个帖子是我从当前应用开发中总结出来的一条规律，出自实际业务中的需求，现在程序运行的非常好。其实我没想过要在数学理论上研究一番然后发表一篇类似论文的东西。数学的发展远远的超过了时代，复杂的数学模型在自然界都很难找到对应的存在，更何况在当前的商业应用中。比如自从毕业后，我还从来没有使用过如复数的计算等东东。

当然了，如果各位是数学方面的专业人才，是应该研究研究，数学理论的发展就看你们的了。

简单的说如果能写出这种公式了
这类问题直接用for从小到大就可以了
f[0]=XXX;f[1]=XXX;f[3]=XXX;
for(x=3;x<n;x++)
{
f[x]=(f[x/4-1]+f[x/6-2])/f[x-2];
}

50 楼 buaawhl 2008-06-24

49 楼 mingliangfeng 2008-06-24

引用

48 楼 csf177 2008-06-23

Trustno1 写道

csf178 写道

Trustno1 写道

引用

要做这个东西其实麻烦在依赖数学比较多复数运算+高次方程+多元方程组
如果能找到相应的lib 就很容易搞定了

与这些东西都无关,
关键的部分在于,你要能证明针对某一类型的递归函数推导出它的通项公式的这一过程是可计算的.
自己手动推导通项公式，在这里没有多大意义.

推导过程组合数学已经有了不过把它用计算机描述出来需要复数运算+高次方程+多元方程组这几个东西

线形/差分递推式的求解当然是有的.
但是我这里强调的是,推导的过程是可计算的.
比如Fib,你首先是要找到生成函数.x/(1-x-x^2) ，然后根据生成函数找到通项公式.
当然通过特征方程找通项公式也很容易,但是特征方程如何找到呢?这样一种找法是不是可计算得?
比如说,A(n)=1+1/A(n-1),A(n) 你能不能找到一种机械的算法找到他的同项公式?

引用

n次方硬件浮点运算很快的你试试Fibonacci的通项公式就知道了比递推快多了......

即便是幂求解很快,问题是通项公式都是那么简单的吗?
比如找硬币问题的通项公式，给你1，2，5分的硬币.就算你找到了特征方程,你仍然要解8个待定系数的，5次方程才能找到通项公式.你觉得这个解法是搞通项公式快,还是动态规划法快?

所以我说复杂搜索楼主的模板处理不了简单的（比如我说的复数运算+高次方程+多元方程组就是指常系数线性的递推关系所有常系数线性齐次的差分方程解都是通项公式都是幂运算没错吧）又有快速计算的通项公式

比如说你又如何从1，2，5分问题的搜索算法找出DP算法呢？其实这个跟递归的形式没有关系重点在于搜索跟DP算法的差距。Functional语言同样要用递归来描述DP算法。

剩下楼主这个模板适用的也就剩下尾递归了。而在算法比较熟练的人手里尾递归几乎不可能出现(要是能写出递推公式来，有多少人傻到直接翻成递归去算)，且不少编译器能识别并转换尾递归所以说这有多大意义？

我觉得在语法树上识别尾递归并且加以优化才算比较有意义的研究建议楼主往这方向发展发展

PS.要是我我能找到任何一个递推的机械计算方法，我第一个就找出
A(n)=A(n-1)+1/n,A(1)=1来哥德巴赫猜想基本就差不多了 hiahia

47 楼 Trustno1 2008-06-23

csf178 写道

Trustno1 写道

引用

要做这个东西其实麻烦在依赖数学比较多复数运算+高次方程+多元方程组
如果能找到相应的lib 就很容易搞定了

推导过程组合数学已经有了不过把它用计算机描述出来需要复数运算+高次方程+多元方程组这几个东西

引用

n次方硬件浮点运算很快的你试试Fibonacci的通项公式就知道了比递推快多了......

46 楼 csf178 2008-06-23

Trustno1 写道

引用

通项公式大部分时候是比较便宜的 CPU那句话说的就是这个意思...... 时间复杂度降了

这个问题,要看你计算n的有多少大,(1+√5)/2]^n,n是25的时候就已经超出65535了.再往上算,Int型就不够往上的大整数计算都是靠快速傅立叶变换做的,FFT 的主要的瓶颈是蝶形运算,这就需要用到非常好的矩阵算法库.如果是大浮点数的话可能还需要快速数论变换.这种计算量就非常之大了.

整型范围不是0-65535呀那是16位机的整型......
n次方硬件浮点运算很快的你试试Fibonacci的通项公式就知道了比递推快多了......

FFT的话......只适用于特定领域的BT需求>_< 一般是超过机器浮点运算表示范围或者精度范围才会用到像这种组合数学游戏是不需要的一般语言本身提供的幂运算足够了......

另外不管怎么变换幂运算只能变得更快不是么..... 要不还不如直接乘了复杂度最多也就O(logN)吧？O(logN)跟O(N)相差可不少

汗学数学的思维就是强大提到幂运算立刻就想到FFT了

45 楼 csf178 2008-06-23

Trustno1 写道

引用

要做这个东西其实麻烦在依赖数学比较多复数运算+高次方程+多元方程组
如果能找到相应的lib 就很容易搞定了

推导过程组合数学已经有了不过把它用计算机描述出来需要复数运算+高次方程+多元方程组这几个东西

44 楼 Trustno1 2008-06-23

引用

通项公式大部分时候是比较便宜的 CPU那句话说的就是这个意思...... 时间复杂度降了

引用

要做这个东西其实麻烦在依赖数学比较多复数运算+高次方程+多元方程组
如果能找到相应的lib 就很容易搞定了

43 楼 csf178 2008-06-23

Trustno1 写道

引用

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是可以直接算的有些需要用程序算
不管哪种都要比递推还快很多

要论速度，通项公式也不便宜.
我觉得LZ需要的是，能够根据一个递归公式自动推算出同项公式的程序.
这个东西，能够作出来就很NB哦.哪怕只是针对某一类递归函数.

通项公式大部分时候是比较便宜的 CPU那句话说的就是这个意思...... 时间复杂度降了

引用

能够根据一个递归公式自动推算出同项公式的程序

要做这个东西其实麻烦在依赖数学比较多复数运算+高次方程+多元方程组
如果能找到相应的lib 就很容易搞定了

所以说实话楼主这个把递归转换成递推意义不大情况太特定了仅仅针对实数域上的递归函数有效

42 楼 Trustno1 2008-06-23

引用

41 楼 csf178 2008-06-21

mingliangfeng 写道

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

40 楼 mingliangfeng 2008-06-21

引用

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

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

引用

不是我打击楼主的想法

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

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

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

39 楼 csf178 2008-06-21

38 楼 rubynroll 2008-06-13

引用

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

例如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的空间会优化运行时间。同时优化空间和时间，对于特定的递归有可能，但不可能找到通用的方法。

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

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论