递归的概念

• 递归函数
  • 举例说明，例如Fabonacci, Ackerman
  • 递归函数的算法设计
• 递归过程
  • 例如Hanoi问题
  • 递归过程的算法设计
• 递归算法的复杂都分析
  • 复杂度函数推导
  • 复杂度渐进阶计算
• 递归算法的调用机制

直接或间接调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数，比如：

斐波那契数列的递归定义为：

int fibonacci(int n){
    if(n <= 1)
        return 1;
    return fibonacci(n-1)+fibonacci(n-2)
}

当然，斐波那契数列也可以直接通过通项公式计算出来，但显然递归的方式更加清晰简单。而且某些问题可能没有或极难求出通项公式，只能用递归求解。下面再看一个例子：

Hanoi 塔问题。古代有一个梵塔，塔内有三个座 A、B、C，A 座上有 64 个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这 64 个盘子从 A 座移到 B 座，但每次只能允许移动一个盘子，并且在移动过程中，3 个座上的盘子始终保持大盘在下，小盘在上。如下图

显然，当只有 1 个盘时，直接从 a 移到 b 即可；当有 n 个盘时，只需要将前 n-1 个盘移到 c，然后将最大的盘移到 b，再将 n-1 个盘移到 b 即可。也就是：

void hanoi(int n, int a, int b, int c){
    if(n>0){
        hanoi(n-1, a, c, b);
        move(a,b);
        //可以是 prinf("把 %d 从 %d 移到 %d", n, a, b)
        hanoi(n-1, c, b, a);
    }
}

系统在调用算法时，会做如下几件事：

1. 将实参指针、返回地址等传送给被调用函数
2. 为被调用的函数分配存储区
3. 将控制转移指向被调用函数的入口
4. 被调用函数执行，并保存计算结果
5. 释放分配的存储区
6. 将控制转移指向原函数

为了实现“后调用先返回”，上面的信息传递与控制转移就要使用堆栈来实现。在递归算法中，需要用到大量的函数调用，因此十分占用存储空间，运行效率也很低。要提高效率，必须尽可能消除递归调用，减少栈操作。

题目：排列问题。设有数组：$R=[r_1, r_2, r_3, \cdots,r_n]$，求其所有可能的排列。（《计算机算法设计与分析》P13）

解：从 $R$ 中排除元素 $a_k$ 元素得到的全排列为 $P(R-a_k)$，那么我们有如下递推关系：
$$ \begin{cases} P(R)=\sum_{k=1}^n a_kP(R-a_k)\\ P(a_k)=a_k \end{cases} $$
在编写代码时，可以考虑将每个元素与第一个元素交换，然后再对后面的元素求全排列。

分治法的基本思想

• 分治算法的基本思想是什么？
• 分治算法的基本框架(三个步骤)
  • 问题分解
  • 子问题递归求解(初始情形求解)
  • 子问题解的合并
• 分治问题算法伪代码描述
  • 分治问题算法的递归实现
• 分治问题算法的复杂度分析
  • T(n) = 分解的复杂度 + 子问题复杂度 + 解的合并复杂度

分治法就是将规模为 n 的分体分为 k 个规模较小的子问题，这些子问题相互独立，并且与原问题相同。递归地解这些问题，然后将子问题的解合并，就可以得到原问题的解。我们可以用以下语言描述：

divide-and-conquer(P){
    if(|P|<=n0){
        solve(P);
    }
    divide P into P1, P2, …, Pk;
    for(i=1;i<=k;i++)
        yi = divide-and-conquer(Pi);
    return merge(y1, y2, …, yk);
}

不妨设分解阈值设为 n0=1，solve(P) 消耗的时间为 1，合并 k 个子问题需要 f(n)，则：

关于如何求解复杂度，可以参考 算法导论——递归算法的时间复杂度求解，我们只需要掌握下面这种方法即可：