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

上一篇文章对递归向非递归转换的原理和过程作了介绍，本篇谈谈具体的代码实现。还是考虑上一篇文章中的递归例子：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框架里面即可：

1. 递归调用出口（exit of recursion）：在当前节点状态为0，即初次遍历至该节点时，会检查递归因子的值。如果能直接计算出来，则计算出来并将状态置为完成；否则，状态递增1，开始计算第一个子节点的值；
2. 递归调用点（branch），包括递归因子的收敛公式，根据其在递归体中出现的顺序安插至case代码体中去；
3. 递归体（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);
  }

 

 

评论

17 楼 Trustno1 2008-06-10  

mingliangfeng 写道

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

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

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

16 楼 mingliangfeng 2008-06-10  

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

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

15 楼 Trustno1 2008-06-10  

引用

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

没有

14 楼 mingliangfeng 2008-06-10  

引用

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

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

引用

楼主给的例子，所需要的空间都是常数，3 或者 100。应该是有递归解的。Right ?

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

13 楼 Trustno1 2008-06-10  

引用

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

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

引用

引用

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 ?

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

mingliangfeng 写道

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

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

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

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

12 楼 buaawhl 2008-06-10  

mingliangfeng 写道

循环for(int i = 10; i <= x; i++)逐步求解在某些情况下有很大的浪费，比如f(x)=f(x/10) + f(x/100)

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

Trustno1 写道

buaawhl 写道

其实，求值递归的意义不大。
递归求值最终都可以用数据归纳法总结出来一个终极公式。连循环形式都不用，一个公式直接出结果。

这种函数必须是原始递归函数.

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

Trustno1 写道

引用

在极端情况下，循环步骤（或者下面层次的递归）需要前面所有层的结果，这个时候，递归转化为循环，就毫无意义

所有的非原始递归的递归函数都没有非递归解,所以对它们无法同时降低空间和时间复杂度.
有兴趣的可以试试这个函数
f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1)) .

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)) .

就是非原始递归？

Trustno1 写道

引用

无论如何，只以有限的数组空间来缓存计算当前父节点需要的子节点的值这种方法是个不错的方向，有可能成为优化非递归程序使用空间的一个手段。

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

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

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

mingliangfeng 写道

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

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

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

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

11 楼 mingliangfeng 2008-06-10  

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

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

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

10 楼 Trustno1 2008-06-10  

引用

无论如何，只以有限的数组空间来缓存计算当前父节点需要的子节点的值这种方法是个不错的方向，有可能成为优化非递归程序使用空间的一个手段。

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

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

9 楼 Godlikeme 2008-06-10  

恩，T1说的不错，可以尝试解决下汉诺塔问题。

8 楼 mingliangfeng 2008-06-10  

当时研究递归向非递归转换的目的，就是想找到一个通用的模板，能够将所有的递归函数转换成非递归的形式；而且这个模板必须能被计算机程序识别，因为转换过程是由程序来完成的。

贴子中的模板实现了这一目标，但确实遗留下一个问题，就是空间的浪费。针对特定的递归公式，buaawhl的方法非常好的解决了这个问题，空间和时间上都得到了非常好的优化。但buaawhl的方法能否用通用的模板来表达，还需要解决如下问题：
1.例子中middleResults的长度的确定，这个不能通过计算来解决，因为转换的过程是静态的
2.循环for(int i = 10; i <= x; i++)逐步求解在某些情况下有很大的浪费，比如f(x)=f(x/10) + f(x/100)

无论如何，只以有限的数组空间来缓存计算当前父节点需要的子节点的值这种方法是个不错的方向，有可能成为优化非递归程序使用空间的一个手段。

非常感谢buaawhl！

7 楼 Trustno1 2008-06-09  

buaawhl 写道

其实，求值递归的意义不大。
递归求值最终都可以用数据归纳法总结出来一个终极公式。连循环形式都不用，一个公式直接出结果。

这种函数必须是原始递归函数.

引用

在极端情况下，循环步骤（或者下面层次的递归）需要前面所有层的结果，这个时候，递归转化为循环，就毫无意义

所有的非原始递归的递归函数都没有非递归解,所以对它们无法同时降低空间和时间复杂度.
有兴趣的可以试试这个函数
f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1)) .

6 楼 buaawhl 2008-06-09  

理论上，递归和循环是等价的。
所有的递归都可以转化为循环，所有的循环都可以转化为递归。

其实，求值递归的意义不大。
递归求值最终都可以用数据归纳法总结出来一个终极公式。连循环形式都不用，一个公式直接出结果。

递归和循环之间的桥接器是尾递归。
我们知道，循环 = 尾递归
所有的递归都可以转化成尾递归（即循环），区别在于转化的代价是多大，好处是多大。

递归的形式有两种，线性递归和树型递归。
线性递归就是函数只调用自己一次。树型递归则是函数调用自己多次。比如楼主的例子，就是树型递归。
不过，树型递归都是可以线性化的，毕竟，运行栈本身就是线性的（一个数组）。
这要看后面的循环步骤（或者下面层次的递归）需要多少层前面的结果。这个层数就是递归转化为循环（尾递归）的代价。比如，楼主的例子，层数就是 3。这时候，转化为循环，就是值得的。

在极端情况下，循环步骤（或者下面层次的递归）需要前面所有层的结果，这个时候，递归转化为循环，就毫无意义。
这通常是遍历的情况。比如，树结构的深度优先遍历。这时候，循环和递归没有什么区别。循环的形式还更难看，还需要自己维护一个不断伸缩的运行栈。

5 楼 lichray 2008-06-09  

这个能转换所有的递归程序吗？
如果能的话那就解决了一个很大很大的问题了......
这个技术不是参数查表吧，用树来表示需求关系，再通过分析递归函数“求导”后的阶数判断树的形状，比要快，但有没有自动删除无效的中间结果的问题，我还不太明白。如果有的话还要在空间上想办法，以彻底打垮参数查表 ：) ，就此解决一个 FP 语言“历史悠久”的问题。

4 楼 buaawhl 2008-06-09  

不错的思考。

其实，楼主的第一篇图文更形象，思路更准确，更应该得到精华。

递归计算向非递归计算转换模板
http://www.iteye.com/post/567240

这一篇实现篇有些误入歧途了。为了通用化而复杂化。
这个问题本身是可以线性化的，不必要树形化。

楼主的代码里面，vlaues (hash map) 保存了所有的中间计算结果，这是没有必要的。这会带来空间的浪费。
楼主的代码本质上是一种查表法（参数值列列表 -> 返回值）。
我们可以简单的用 Method Cache （方法缓存）的方式来实现。
只要用AOP，给这个函数加上Cache缓存（key是 函数名 + 参数列表），就可以轻松实现需要的效果。

第一篇思路篇里面的图很形象。
相当于程序员自己维护一个数组形式的运行栈结构。
在一些支持Continuation的非栈语言中，运行栈其实是树形的运行堆，中间结果都是保留起来的，保留中间结果的这些工作都不需要自己做。
楼主相当于做了一些Continuation的树形运行堆的工作。在栈语言上模拟这种效果，有些事倍功半的感觉。

------------------------------

这类问题其实就是保存前几步中间计算结果的问题。

对于这个问题本身来说
f(x) = f(x-1) + f(x-3)
f(x) = 10 (x < 3)

其实是很简单的，只需要用一个长度为3的数组保存中间结果就可以了。

fibonacci(int x){
  if(x < 3)
    return 10;


  int[] middleResults = new int[3]{10,10,10};
  int result = 0;

  for(int i = 10; i <= x; i++){
    result = middleResults[0] + middleResults[2];
    move(middleResults);
    middleResults[0] = result;
  }

  return result;
}

void move(int[] array){
  int k = array.length;
  int limit = k – 1;
  for(int i = 0; i < limit; i++){
    array[i+1] = array[i];
  }
}

move 方法主要用来移动中间结果数组里面的中间结果。
其实完全可以用一个 queue 队列来保存中间结果。直接把用过的 queue head 丢弃，把后面的结果加在队尾。正如楼主的代码里面用的queue结构。
只是为了更加形象地表达数组（运行栈）的结构，因此这里用了定长数组。


代码没有调试过，只是一个大概意思。
这段代码是循环形式，也可以写成递归形式，中间结果数组作为参数进行传递。

-------------------------

这个问题本身是Fibonacci问题的变种

Fibonacci问题描述：
1头母牛，出生后第3年，就开始每年生1头母牛，按此规律，第n年时有多少头母牛。
f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2)

Fibonacci数列：1,1,2,3,5,8,13,,21,34........

Fibonacci问题变种A描述：
1头母牛，出生后第4年，就开始每年生1头母牛，按此规律，第n年时有多少头母牛。
f(1)=1
f(2)=1
f(3)=1
f(n)=f(n-1)+f(n-3)

Fibonacci数列：1, 1, 1, 2, 3, 4, 6, 9,13,19,28........

Fibonacci问题通用描述：
1头母牛，出生后第x年，就开始每年生1头母牛，按此规律，第n年时有多少头母牛。
令k = x - 1
f(1)=1
…
f(k)=1
f(n)=f(n-1)+f(n-k)

-------------------------------------

递归函数：f(x) = ( f(x-1) + f(x-3) + x) / f(x-2), f(x) = 10 (x < 3)
同样可以类似解决。

f(double x){
  if(x < 3)
    return 10;


  double[] middleResults = new double[3]{10,10,10};
  double result = 1;

  for(int i = 10; i <= x; i++){
    result = (middleResults[0] + middleResults[2] + i) / middleResult[1];
    move(middleResults);
    middleResults[0] = result;
  }

  return result;
}

void move(int[] array){
  int k = array.length;
  int limit = k – 1;
  for(int i = 0; i < limit; i++){
    array[i+1] = array[i];
  }
}

3 楼 Godlikeme 2008-06-09  

如果是递归算法，存在重复计算 低阶问题域的问题，有必要解递归，避免重复计算。如果是纯递归调用，没必要转为非递归方式。
比较简单的纯递归调用问题直接循环就好了，复杂点递归算法压栈加hashMap，这些应该算法书上都有讲。

2 楼 mingliangfeng 2008-06-09  

模板中case 3是递归体里面的公式。将例子中的递归函数大卸4快，安插至模板中就可以了。

1 楼 Godlikeme 2008-06-09  

这个模板是指直接替换最后的那个case 3里面的公式就可以，是吧。