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

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

 

 

评论

37 楼 mingliangfeng 2008-06-13  

<div class='quote_title'>引用</div>
<div class='quote_div'>1. 空间： <br/>递归时堆栈容易溢出说明空间利用率上没有得到优化，但是相比之下，如果转换成循环也不能优化空间，又何必多此一举呢？ <br/><br/>递归－&gt;使用栈空间，循环-&gt;使用堆空间。 <br/><br/>有些语言实现可以在堆上分配栈，那递归和循环就没有本质区别了。</div>
<p> </p>
<p>不知道你指的有些语言是指哪些语言？在java, c#, PLSQL等语言下，栈的溢出比out of memory经常得多。</p>
<p> </p>
<div class='quote_title'>引用</div>
<div class='quote_div'>2. 时间： <br/>采用cache等效于缓存中间计算结果，优化运行时间。同样，可以采用只cache一个“窗口”来解决cache的空间问题。如以上各位总结，确定这个“窗口”并不容易，而且不能保证这个“窗口”是足够窄的，这时只好限定cache大小，又以时间来换取空间了。</div>
<p> </p>
<p>就空间来讲确实没有优化；但是用来cache的空间会优化运行时间。同时优化空间和时间，对于特定的递归有可能，但不可能找到通用的方法。对于用语言自身的递归特性实现的递归而言，运行时间是瓶颈所在。试试例子中的递归实现就知道了：</p>
<p> </p>
<pre name='code' class='java'>public static double recursion(double x) {  
  if (x &lt; 3)  
    return 10.0;  
 
  double f1 = recursion(x - 1);  
  double f2 = recursion(x - 3);  
  double f3 = recursion(x - 2);  
  return (f1 + f2 + x) / f3;  
}  </pre>
<p> </p>

36 楼 rubynroll 2008-06-13  

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

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

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

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

35 楼 Elminster 2008-06-12  

Trustno1 写道

引用

这种优化有可能在一定程度上降低堆栈的使用,但还是很容易溢出.

这个函数实际上是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)), 一直是被拿来当作平摊分析的经典例子的 ...

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

34 楼 sunnyshuhai 2008-06-12  

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

33 楼 woods 2008-06-12  

看完帖子受教了 谢谢:-)

32 楼 Trustno1 2008-06-11  

引用

这种优化有可能在一定程度上降低堆栈的使用,但还是很容易溢出.

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

31 楼 simohayha 2008-06-10  

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

30 楼 buaawhl 2008-06-10  

Ruby 也是栈语言，也有运行栈和运行栈溢出吗？
我以为 Ruby 是解释执行树，只可能有内存堆溢出，不会有运行栈溢出。

函数cache中，多个参数的cache比较麻烦。key 值比较难取。
一般来说， key = 参数名1 + 参数值1 + 参数名2 + 参数值2 + ... 构成的一个字符串。
比如楼上做的T1的例子中，
key = m3n8

更好的方式是用内存关系数据库作为 cache
列名就是参数名。取出返回值的时候也方便。

select return-value from cache where
参数名1 = 参数值1 and 参数名2 = 参数值2 ...

select return-value from cache where
m = 3 and n = 8

当然，前提是该内存关系数据库非常快，和hashmap一样快。

29 楼 rubynroll 2008-06-10  

T1的公式也可以按此法优化:

# f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1))

def f(m, n, cache = {})
  cache[m] ||= {}
  unless cache[m][n]
	  if m == 0
	    cache[m][n] = n + 1
	  elsif n == 0
	    cache[m][n] = f(m-1, 1, cache)
	  else
	    cache[m][n] = f(m-1, f(m, n-1, cache), cache)
	  end  
	end
  cache[m][n]
end

puts "f(3,8) = #{f(3,8)}"

这种优化有可能在一定程度上降低堆栈的使用,但还是很容易溢出.

28 楼 rubynroll 2008-06-10  

排除有些语言不能使用递归的因素外,实际上可以采用保存中间值的方法优化递归,这种优化是具备普遍性(可以模板化)的.

以下是两个Fibonacci的Ruby实现, 第一个是未优化的,第二个是优化过的:

def fib(x)
	case x
	when 0
		0
	when 1
		1
	else
		fib(x-1) + fib(x-2)
	end
end

def fib2(x, cache = {})
	unless cache[x]
	  cache[x] = case x
			when 0
			  0
			when 1
	  		  1
			else
			  fib2(x-1, cache) + fib2(x-2, cache)
			end
	end
	cache[x]
end

未优化的fib(40)大概要计算1分钟, 优化过的fib2(1000)不到1秒钟.

27 楼 lichray 2008-06-10  

buaawhl 写道

Memorization就是指支持Lazy语法的语言？
支持Lazy语法的语言，会自动保存和使用中间计算结果。Right ?

完全两码事啊... Memorization 是实现技术，Lazy 是语义，而且两者之间没有关系。前者就是你所说的参数查表，后者是要求保存运算过程（不是参数->结果对！）的一种语言的语义。

26 楼 mingliangfeng 2008-06-10  

引用

你需要的是一个支持Memoization的求值器，而不是通用的递归转化模板.在Java内嵌Jruby,Groovy,Scala,JavaScript选择非常多。没有必要专门搞这种东西.

Trustno1不了解我遇到的系统的背景。递归向非递归的转换是一个公式系统中的一小部分。公式系统利用代码生成机制，根据用户选择将公式生成不通的实现，比如java, c#, ruby, 或plsql。用内嵌语言的方法显然行不同。

两位高手的讨论让作者对递归算法有了更深的认识，真是长见识了！

25 楼 eyes_shine 2008-06-10  

长见识了。。

24 楼 buaawhl 2008-06-10  

Trustno1 写道

引用

将原始递归函数的非原始递归形式变换为原始递归

这个是否能够楼主的需求？

原始递归是不是就是 尾递归？

我上面提到过，所有的原始递归函数的第n+1步都能通过第n步和第0步结果直接运算获得,所以就是尾递归.

引用

支持Memoization的求值器
就是支持 Continuation 或者 查表法( Cached {Param Value -> Return Value}) 。Right ?
这类语言都是非栈语言吗？

什么叫非栈语言?
Memorization实际上就Haskell的call_by_need,每一个表达式都只计算一次.一般的语言都是call_by_name,要做memorization就得借助第三方库.

非栈语言就是不用运行栈的语言。有可能采用执行结点树等方式。
我忘了哪里看到了的概念。叫做 Non-Stack Language。栈语言叫做Stack languange，比如 java, c.

Memorization就是指支持Lazy语法的语言？
支持Lazy语法的语言，会自动保存和使用中间计算结果。Right ?

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

http://realazy.org/blog/2008/04/22/javascript-memoization/

引用

JavaScript Memoization
2008-04-22 23:57 JS / Dom
Memoization 是一种将函数返回值缓存起来的方法，在 Lisp, Ruby, Perl, Python 等语言中使用非常广泛。随着 Ajax 的兴起，客户端对服务器的请求越来越密集（经典如 autocomplete），如果有一个良好的缓存机制，那么客户端 JavaScript 程序的效率的提升是显而易见的。

Memoization 原理非常简单，就是把函数的每次执行结果都放入一个散列表中，在接下来的执行中，在散列表中查找是否已经有相应执行过的值，如果有，直接返回该值，没有才真正执行函数体的求值部分。很明显，找值，尤其是在散列中找值，比执行函数快多了。现代 JavaScript 的开发也已经大量使用这种技术。

http://en.wikipedia.org/wiki/Memoization

Memoization
From Wikipedia, the free encyclopedia

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs. Memoization has also been used in other contexts (and for other purposes than speed gains), such as in simple mutually-recursive descent parsing by Norvig,[1] in a general top-down parsing algorithm by Frost, Hafiz and Callaghan[2][3] that accommodates ambiguity and left-recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement.

.....

Automatic memoization

While memoization may be added to functions internally and explicitly by a computer programmer in much the same way the above memoized version of factorial is implemented, referentially transparent functions may also be automatically memoized externally.[1] The techniques employed by Norvig have application not only in Common Lisp (the language in which his paper demonstrated automatic memoization), but in various other programming languages. Applications of automatic memoization have also been formally explored in the study of term rewriting[5] and artificial intelligence.[6]

In those programming languages where functions are first or second-class objects (such as Lua, with its first-class functions), automatic memoization can be implemented by replacing (at runtime) a function with its calculated value once a value has been calculated for a given set of parameters. The function that does this value-for-function-object replacement can generically wrap any referentially transparent function. Consider the following pseudocode (where it is assumed that functions are first-class values):

这段话的意思是，缓存返回值，程序员可以自己做。一些语言也可以自动做到这一点。使用类似 Thunk (Lazy Singleton) / Hash Map 结构，把中间计算结果保存起来。

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

根据上述 link 的例子，自己做这个Cache也很简单。只需要在函数出入口处对参数和返回值进行截获处理即可。

引用

values // hash map

f(x) {
  v = values.get(x);
  if v not null return v

  ret = ... calculation

  values.set(x, ret);
  return ret;
}

// before method invoking
  v = values.get(x);
  if v not null return v

// after method invoking
  values.set(x, ret);

这样的AOP Advice代码，可以采用AOP技术自动生成插入到代码中。

23 楼 Trustno1 2008-06-10  

引用

将原始递归函数的非原始递归形式变换为原始递归

这个是否能够楼主的需求？

原始递归是不是就是 尾递归？

我上面提到过，所有的原始递归函数的第n+1步都能通过第n步和第0步结果直接运算获得,所以就是尾递归.

引用

支持Memoization的求值器
就是支持 Continuation 或者 查表法( Cached {Param Value -> Return Value}) 。Right ?
这类语言都是非栈语言吗？

什么叫非栈语言?
Memorization实际上就Haskell的call_by_need,每一个表达式都只计算一次.一般的语言都是call_by_name,要做memorization就得借助第三方库.

22 楼 buaawhl 2008-06-10  

Trustno1 写道

buaawhl 写道

Trustno1 写道

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

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

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

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

将原始递归函数的非原始递归形式变换为原始递归

这个是否能够楼主的需求？

原始递归是不是就是 尾递归？

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

Trustno1 写道

mingliangfeng 写道

引用

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

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

我不知道Cooper变化的要求到底是怎么样，有时间去查一查。目前出现递归计算的具体业务主要在金融保险方面，比如保险保费的计算。这些业务中需要使用递归，但递归具有业务意义，其形式不是很复杂，绝不会出现Trustno1所列出的这种递归：f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1))。

就我们所讨论的递归函数的复杂度而言，应该远远超过了目前所面对的业务应用的范围。

你需要的是一个支持Memoization的求值器，而不是通用的递归转化模板.在Java内嵌Jruby,Groovy,Scala,JavaScript选择非常多。没有必要专门搞这种东西.

支持Memoization的求值器
就是支持 Continuation 或者 查表法( Cached {Param Value -> Return Value}) 。Right ?
这类语言都是非栈语言吗？

21 楼 Trustno1 2008-06-10  

mingliangfeng 写道

引用

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

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

我不知道Cooper变化的要求到底是怎么样，有时间去查一查。目前出现递归计算的具体业务主要在金融保险方面，比如保险保费的计算。这些业务中需要使用递归，但递归具有业务意义，其形式不是很复杂，绝不会出现Trustno1所列出的这种递归：f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1))。

就我们所讨论的递归函数的复杂度而言，应该远远超过了目前所面对的业务应用的范围。

你需要的是一个支持Memoization的求值器，而不是通用的递归转化模板.在Java内嵌Jruby,Groovy,Scala,JavaScript选择非常多。没有必要专门搞这种东西.

20 楼 mingliangfeng 2008-06-10  

引用

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

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

我不知道Cooper变化的要求到底是怎么样，有时间去查一查。目前出现递归计算的具体业务主要在金融保险方面，比如保险保费的计算。这些业务中需要使用递归，但递归具有业务意义，其形式不是很复杂，绝不会出现Trustno1所列出的这种递归：f(0,n)=n+1, f(m,0)=f(m-1,1), f(m,n)=f(m-1,f(m,n-1))。

就我们所讨论的递归函数的复杂度而言，应该远远超过了目前所面对的业务应用的范围。

19 楼 Trustno1 2008-06-10  

buaawhl 写道

Trustno1 写道

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

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

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

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

18 楼 buaawhl 2008-06-10  

Trustno1 写道

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

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

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