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

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

 

 

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

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

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

不错的思考。

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

递归计算向非递归计算转换模板
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];
  }
}

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

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

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

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

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

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

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



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

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

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

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

非常感谢buaawhl！

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