浅谈尾递归的定义和判定方法

2013-12-21

今天周六，还赖在床上时，突然想到了尾递归，虽然尾递归见得多了，也大概知道尾递归的优化原理，但是具体的定义感觉还是不太清晰，于是躺在床上想了下，自己给尾递归下了一个定义,将来有空给出数学上的证明和实现方法。

首先给出尾递归的几种形式，方便下文描述（为方便书写，使用python伪代码，虽然python没有实现尾递归）

然后为了简化逻辑，首先假设编程语言只有函数，函数调用和结构体，其他的类，接口，方法都可以等价于函数或结构体，且所有函数都有返回值，现代编程语言中常见的void也算是一种特殊的返回值

第一种是最常见的函数尾递归调用自身：

def fact(n, acc=1):

if n <= 1:
      return acc
else:
      return fact(n-1, acc*n)

另一种是几个函数相互尾递归调用：

n = 0

def recur1(acc=1):
  if n % 2 == 0
    return recur2(acc)
  else if n < 1000:
    return recur1(acc+1)
  else:
    return acc

def recur2(acc=1):
  if n % 2 == 0:
    return recur2(acc+2)
  else:
    return recur1(acc)

再给一个非尾递归的例子做对比：

n = 0

def recur1(acc=1):
  if n % 2 == 0
    return recur2(acc)+1
  else if n < 1000:
    return recur1(acc+1)
  else:
    return acc


def recur2(acc=1):
  if n % 2 == 0:
    return recur2(acc+2)
  else:
    return recur1(acc)+2

上面只是随手写的例子，姑且不要看它们是否有实际意义，只看尾递归。

因为尾递归优化的原理是把原本的一层层很多次函数调用以及函数调用栈空间导致栈空间大量膨胀，优化成可以在尾递归调用时不重复分配更多栈空间的形式，或者直白点，把尾递归优化成循环，把汇编级的call指令优化成jmp

如上面代码可以很简单地看出，demo1和demo2都是尾递归，因为return的内容不是基本数值（或者变量，常量，都统一称作基本数值），就是调用自身，或者两个函数尾部互相调用。

为了简化逻辑，定义：所有基本数值或者常量，变量，都是“在任意函数集中可尾递归的”

同样，给所有函数都加上一个标签（这个标签在本次编译活动中可见，原因见下文），分别表示“在函数集合C中可尾递归的”（简单称作“可尾递归的”），“在函数集合C中不可尾递归的”（为什么这么说下文会说原因），“在函数集合C中依赖XX,XX函数集合可尾递归的”（这个标签表示这个函数依赖一个函数集合，如果这个函数集合内所有函数都是“可尾递归的”，则这个函数本身也是“可尾递归的”）

然后可以归纳出一个简单的定义，

定义1：

对于一个函数集合C1,如果其中的所有函数都是“可尾递归的”，或者是“依赖函数集合C1的子集可尾递归的”，则这个函数集合C1和其中所有函数都是“可尾递归的”，否则就是“在函数集合C1中不可尾递归”。

然后给出获得函数的尾递归依赖函数集（依赖这个函数集合以成为可尾递归的）的定义：

定义2：

    在函数集C中，对任意函数Func，获得它的函数体的所有最后可能执行的函数调用或者基本数值（或者是所有return语句后面的内容），得到一个函数集S0，将函数集S0分为函数集C中可尾递归的函数集S1，函数集C中不可尾递归的函数集S2，函数集C中依赖某函数集可尾递归的函数集S3。
    如果函数集S2不为空，则函数Func在函数集C中不可尾递归，停止后面步骤。
    然后，函数Func的尾递归依赖函数集就是S3中每个函数的尾递归依赖函数集的并集的结果再并上S1.得到的结果S就是函数Func在函数集C中的尾递归依赖函数集(尾递归依赖函数集不包括函数Func本身）。
另外，基本数值或常量或变量作为“可尾递归的”，它们的尾递归依赖集是空集。

有了这两个定义，可以得到尾递归的判定方法：

在一次编译活动中，要判断函数F是否是尾递归的，按以下步骤操作：

如果本次判断被要求在某个函数集上进行，则把这个函数集称作C，否则初始化一个空集C，
把F0加入函数集C
根据定义2找到函数F的尾递归依赖函数集C1，如果得出函数F是不可尾递归的，则判定结束，函数F是不可尾递归的，整个函数集C也是不可尾递归的
将第三步的函数集C1并入函数集C得到新函数集C
得到结果，函数集C内的所有函数在函数集C内是可尾递归的

根据上面定义，对demo2的代码进行分析，

初始化集合C为空集，在函数集C上从函数recur1开始进行分析（此时C={recur1}）
首先找到函数recur1的尾递归依赖函数集C1={ recur2, acc }，
然后C1中acc是变量，是在函数集C中可尾递归的，
函数recur2的尾递归依赖集是C2={recur1}，把C2并入C1，此时C1={recur2, acc}(因为C1是recur1的尾递归依赖函数集，不包括recur1自身)
然后，把C1并入C，得到C={recur1, recur2, acc}
所以recur1, recur2在函数集C={recur1, recur2, acc}中是可尾递归的，判定完毕。

再对demo3的代码进行同样的分析，得到recur1, recur2的函数依赖集C={recur1, recur2, acc, + }
这个时候怎么判断recur1和recur2在函数C中是不是可尾递归的呢？这个函数+怎么处理呢？我们无法知道函数 + 在函数集C中是否是尾递归的。

因为尾递归优化是在某一次编译活动中进行的，对这次编译活动中所有的源代码的编译结果进行控制，而对已经编译好的函数库无法控制无法修改，也就没有办法对已经编译的函数库进行尾递归优化的修改，所以已编译的函数库对之后的编译活动都是不可尾递归的，比如函数+，这也是我上文多次提到函数集合和可尾递归的标签是在一次编译活动中的原因。

如果函数+是已经存在的已经编译好的函数库或者语言内置函数，则它当然在函数集C中不可尾递归，因为它已经无法修改的，所以demo3是不可尾递归优化的。
而如果函数+是用户定义的源码，在本次编译中一起编译，且它的源码的尾递归依赖集也全部可以归入到函数集C中，则demo3在这种情况下是可以尾递归优化的，当然这中情况不太可能哈。

到这里，尾递归的定义和判定方法应该说得很清楚了，当然，这只是我躺床上想出来的，如果有错漏，欢迎指正。

严格的数学证明和尾递归的代码实现的方法有空再写，现在起床吃饭去。