递归与分治

递归的概念

  • 递归函数
    • 举例说明,例如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),则:

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

计算过程 $$ \begin{align} T(n)&=3T(n/2)+kn\\ &=3\big(3T(n/4)+kn/2\big)+kn\\ &=9\big(3T(n/8)+kn/4\big)+3kn/2+kn\\ &\cdots\\ &=3^xT(n/2^x)+\sum_{i=0}^x \left(\frac{3}{2}\right)^ikn \end{align}\\ $$ $$ 当 n=2^x 时,T(n/2^x)=O(1),故 x=\log_2 n\\ \begin{align} T(n)&=3^{\log_2 n}+\sum_{i=0}^{\log_2 n} \left(\frac{3}{2}\right)^ikn\\ &=2^{\log_2 3 \log_2 n}+2kn\cdot(\left(\frac{3}{2}\right)^{\log_2 n+1}-1)\\ &=n^{\log 3}+2kn\cdot(\frac{3n^{\log 3}}{2n}-1) &=O(n^{\log3}) \end{align} $$