关于递归

注： 最近再读SCIP，看到第一章时被Recurion Process、Recursive Procedure、Tail-Recursive、Tree-Recursive等概念搞的有些头晕，google了以下，发现一篇文章解释的很是简练清楚。

~akayabas/COSC455_Spring2000/Recursion_Iteration.htm

递归

---

1. 介绍

递归技术允许我们将原问题分解为一个或多个形式上相似的子问题

---

2. 例子：级数

级数(n!)的定义如下：

   n! = 1 * 2 * 3 * .... * (n-2) * (n-1) * n

可以根据定义写出如下迭代形式的实现

int fact(int n) {
   int i;
   int result;
  
   result = 1;
   for (i = 1; i <= n; i++) {
      result = result * i;
   }
   return result;
}

还可以写出递归形式的实现

int fact(int n) {
    if (n == 1) return 1;
    return n * fact(n - 1);
}

比较这两个版本：

• 迭代版本中包含两个局部变量，而递归版本中只有一个
  
• 迭代版本中有三条声明语句，而递归版本中只有一条
  
• 迭代版本在返回前需要将结果存储在中间变量中，而递归版本在一个表达式中完成计算和返回
  

可以看到，递归简化了级数的实现：让计算机去做更多的事情，从而让程序员作更少的事情。

---

3. 定义

递归函数可以进行如下分类：
The recursive functions are characterized based on:

1. 是否调用自身(直接或间接递归)
2. 是否存在未决操作(尾递归(tail-recursive)或非尾递归)
   
3. 调用模式的结构——是否未决操作本身也是递归的(线性递归或树状递归)
   

直接递归:

递归函数的函数体中存在显式的自我调用时，被称为直接递归。例如，函数foo中包含自我调用，因此是直接递归。

int foo(int x) {

   if (x <= 0) return x;

   return foo(x - 1);
}

间接递归:

函数foo被称为间接递归，如果它包含对另一个函数的调用而该函数最终会调用函数foo。

下面的一对函数属于间接递归。由于他们都互相调用，因此又被称为互递归函数

int foo(int x) {

   if (x <= 0) return x;

   return bar(x);
}

int bar(int y) {
   return foo(y - 1);
}

尾递归(tail recursion):

一个递归函数被称为尾递归函数，如果在递归调用的过程中不存在未决操作的话。

尾递归函数通常被描述为：“返回上次递归调用得到的值作为函数的返回值。”尾递归具有很大的价值，因为在(递归)计算过程中需要维护的信息量与递归调用次数是无关的。某些现代计算机系统在实际上通过迭代过程来完成尾递归函数的计算。

“声名狼藉"的级数函数通常被写成非尾递归的形式：

int fact (int n) { /* n >= 0 */

   if (n == 0)  return 1;

   return n * fact(n - 1);
}

注意到这里在每次递归调用返回时存在一个未决操作——乘法运算。只要存在未决操作，递归函数就是
非尾递归的。所有未决操作的相关信息必须被存储，因此是与递归调用的次数密切相关的。

级数函数也可以被写成尾递归形式：

int fact_aux(int n, int result) {

   if (n == 1) return result;

   return fact_aux(n - 1, n * result)
}


int fact(n) {

    return fact_aux(n, 1);
}

辅助函数fact_aux被用来保证不需要改变fact(n)的调用形式。实际的递归函数是fact_aux，而不
是fact。注意fact_aux中不存在未决操作。通过递归调用得到的值被不加修改的直接返回。计算过程
中需要维持的信息量是常数(变量n和变量value的值)，与递归调用的次数无关。

线性和树状递归:

递归函数的另一种分类方式是递归调用是如何增长的。两种基本形式是"线性"和"树状"。

一个递归函数被称为线性递归，如果其中的未决操作(如果存在的话)并不涉及到递归调用的话。

例如，“声名狼藉"的fact函数是线性递归。其未决操作是简单的乘以一个标量，并不涉及对fact的递归调用。

一个递归函数被称为树状递归(或非线性递归)，如果未决操作也是递归调用的话。

Fibonacci函数为树状递归提供了一个经典的例子。Fibonacci数列按如下规则定义：

   fib(n) = 0  if n is 0,
          = 1  if n is 1,
          = fib(n-1) + fib(n-2) otherwise

例如，前7个Fibonacci数分别是:

   Fib(0) = 0   
   Fib(1) = 1   
   Fib(2) = Fib(1) + Fib(0) = 1
   Fib(3) = Fib(2) + Fib(1) = 2
   Fib(4) = Fib(3) + Fib(2) = 3
   Fib(5) = Fib(4) + Fib(3) = 5
   Fib(6) = Fib(5) + Fib(4) = 8

这样引出了如下的实现：

int fib(int n) { /* n >= 0 */

   if (n == 0) return 0;

   if (n == 1) return 1;

   return  fib(n - 1) + fib(n - 2);
}

注意到函数体中的未决操作是另一次递归盗用，因此fib函数是树状递归。

---

4. 将递归函数转换为尾递归

一个非尾递归函数经常可以借助于一个附注参数被转换为尾递归函数，该参数被用于存放结果。基本思想是将未决操作合并到辅助参数中，从而消除未决操作。该技术通常还需要一个辅助函数，这只是为了保持文法的清晰和对外隐藏辅助参数的实际使用。

例如，可以通过使用两个用于存放结果的辅助参数来实现一个尾递归的Fibonacci函数。原有的树状递归函数fib需要两个附注参数来存放结果，这并不奇怪，因为它涉及两个递归调用。要计算fib(n)，则调用fib_ax(n 1 0)

int fib_aux(int n, int next, int result) {

  if (n == 0) return result;
  return fib_aux(n - 1, next + result, next);
}

树状递归的fib() 函数是一个复杂度为O(2^n)的算法，换句话说当n递增1时问题尺寸加倍。另一方面，线性递算法则是O(n)的，换句话说，需要的工作量是线性增长的。

---

References: Thomas A. Anastasio, Richard Chang.