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

我不知道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 ?
这类语言都是非栈语言吗？

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



什么叫非栈语言?
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/


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也很简单。只需要在函数出入口处对参数和返回值进行截获处理即可。



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

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

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

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

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

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

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

以下是两个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秒钟.

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)}"

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

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一样快。