博客

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. 是否调用自身(直接或间接递归)</