通用尾递归优化算法（包括自我尾递归和A->B, B->C, C->A的复杂尾递归的优化）

关于通用的尾递归的识别，请参看我的另一片博文《浅谈尾递归的定义和判定方法》

本文讲述我对怎么对各种复杂的尾递归的通用性优化方法的思考。

因为是思考过程中写的，如有疏漏，非常欢迎指正。

为了方便描述，本文代码使用Scheme Racket，部分地方可能会带有一点Python或者伪代码。

首先给出一个简单的尾递归调用的例子：

(define (foo n)
  (if (> n 20140000)
    (begin (display "foo") n)
      (bar (+ n 1))))

(define (bar n)
  (if (> n 20130000)
    (begin (display "bar") n)
    (foo (+ n 2))))

(display (foo 1234))

这是一个没有意义的例子，因为20130000<20140000，所以始终会输出bar2013000x，不过用来分析尾递归足够了。

上面例子的结果是bar20130002，如果没有实现尾递归优化或者尾调用优化，则会栈溢出。这是一个很简单也很普遍的尾递归的例子，当foo==bar时，这个例子就退化成尾递归调用自身的最简单尾递归的形式。至于更复杂的尾递归情形，与这个例子大同小异，所以本文就用这个例子描述。

在我的另一篇博客中描述了一种基于continuation的计算模型，可以用来实现带有continuation的LISP，所以本文也基于continuation给出两种自己的方法。

第一种方法是基于我另一篇博客中描述的f(env, continuation)=(env2, continuation2)的LISP计算模型的。因为根据我之前的博客《浅谈尾递归的定义和判定方法》，解释器/编译器在执行代码前就可以知道，在函数集{foo, bar}中，其中所有函数都是尾递归的。这样在执行到foo函数中的调用函数bar时，只要将continuation的指针指向bar函数的函数体开头，把bar的参数放入env down之后的新env中即可，得到的env和cont用来进行下一次f(env, cont)=(env2, cont2)。相当于不改变函数本身的结构，而是将函数调用简化成一次类似goto的操作。这其实应该是尾调用优化，不过基于我这种计算模型没有堆栈概念的特点，这种尾调用优化差不多具有了尾递归优化的全部优点。

第二种方法是基于continuation和状态机。将函数foo和bar分成多个单元，为了方便描述，起名逻辑单元（普通代码），分支单元（if判断等），尾递归调用单元（尾递归调用另一个函数的部分），结尾单元（非尾递归调用的函数foo/bar的最后执行的代码）。这种方法就是将foo和bar函数完全改造成一个新的函数，这个函数包括了函数foo和bar的全部逻辑，同时具有函数foo和bar的全部功能，是一种replacement。

下面给出第二种方法的scheme伪代码，主要描述思路和方法，具体完善之后再做：

(define f (state params)
  "state可以是很多个状态，包括开始，结束，处于每个逻辑单元和分支单元的状态等"
  (let* ((current-params params) ;; 当前参数。这两个symbol实际上应该使用特殊的不会被用户使用的名称，比如特殊名称规则，只能被系统使用，不能用户代码中使用的等
         (cond 根据foo和bar中的所有分支单元的逻辑的状态机，接收一个状态，返回下一个状态))
    (return-value nil))
  (while (not (= state "end"))
         (begin
           修改env，清空当前层除函数f中固定的symbol如cond,current-params之外的所有key=>value对。并且把current-params中的值
           根据state执行不同的逻辑单元，或者根据state执行不同的结尾单元并修改return-value
           根据state执行不同的尾递调用单元，主要是调整current-params
           ))
  return-value)

经过这种代码级别的转换后，尾递归调用自然就转换成了一个循环的方式，从而完成了尾递归优化，不再需要解释器或编译器做其他处理，把转换后的代码直接解释执行或编译执行就可以了。

水平所限，难免缺漏。如果发现问题，欢迎指正，如果有我没说明白的，也欢迎邮件联系。谢谢！