递归

递归的算法思想

• 基本思想

• 把一个问题划分为一个或多个规模更小的子问题，然后用同样的方法解规模更小的子问题

• 递归算法的基本设计步骤

• 找到问题的初始条件（递归出口），即当问题规模小到某个值时，该问题变得很简单，能够直接求解

• 设计一个策略，用于将一个问题划分为一个或多个一步步接近递归出口的相似的规模更小的子问题

• 将所解决的各个小问题的解组合起来，即可得到原问题的解

设计递归算法需要注意以下几个问题

• 如何使定义的问题规模逐步缩小，而且始终保持同一问题类型？

• 每个递归求解的问题规模如何缩小？

• 多大规模的问题可作为递归出口？

• 随着问题规模的缩小，能到达递归出口吗？

递归设计实例

1. 计算 f(n) = 2ⁿ

f(n) = 2 × 2<sup>n-1</sup> = 2 × f(n-1)f(1) = 2<sup>1</sup> = 2

Programf(n)

1. if n=0 then return 1

2. else return 2 * f(n-1)

2. Hanoi 问题

1. 将前 n-1 个圆盘从 A 柱借助于 C 搬到 B 柱

2. 将最后一个圆盘直接从 A 柱搬到 C 柱

3. 将 n-1 个圆盘从 B 柱借助于 A 柱搬到 C 柱

4. Hanoi(n, A, B, C)if n=1 then move(1, A, C)elseHanoi(n-1, A, C, B)move(1, A, C)move(n-1, B, A, C)

T(n) = 2T(n-1) + 1T(1) = 1

3. Selection sort

• 基本思想

• 把所有牌摊开，放在桌上，伸出左手，开始为空，准备拿牌

• 将桌上最小额牌拾起，并把它插到左手所握牌的最右边

• 重复上一步，直到桌上的所有牌都拿到你的左手上，此时左手上所握得牌便是排好序的牌

• SelectionSort(i)if i >= n then return 0elsek = ifor j <- i+1 to n doif A[j] < A[k] thenk <- jif k != i then A[i] <-> A[k]SelectionSort(i+1)

T(n) = T(n-1) + nT(1) = 1

Java 代码实现

package sort;
import java.util.Arrays;
public class RecursiveSelectionSort {
  public static void main(String[] args) {    double[] list = {3, 1, 5, 7, 2};    sort(list);    /*    for (int i = 0; i < list.length; i ++)      System.out.print(list[i]+"    ");    */    System.out.println(Arrays.toString(list));  }    public static void sort(double[] list) {    sort(list, 0, list.length-1);  }    public static void sort(double[] list, int low, int high) {    if (low < high) {      double currentMin = list[low];      int currentMinIndex = low;            for (int i = low+1; i <= high; i++) {        if (currentMin > list[i]) {          currentMin = list[i];          currentMinIndex = i;        }      }            list[currentMinIndex] = list[low];      list[low] = currentMin;            sort(list, low+1, high);    }  }}

4. 生成排列

• 问题是生成{1, 2, ...., n}的所有 n!排序

想法 1： 固定位置放元素

• 假设我们能够生成 n-1 个元素的所有排列，我们可以得到如下算法：

• 生成元素{2, 3, ...., n}的所有排列，并且将元素 1 放到每个排列的开头

• 接着，生成元素{1, 3, ...., n}的所有排列，并且将元素 2 放到每个排列的开头

• 重复这个过程，直到元素{2, 3, ...., n-1}的所有排列都产生，并将元素 n 放到每个排列的开头

• T(n) = nT(n-1) + n

想法 2： 固定元素找位置

• 首先，我们把 n 放在位置 P[1]上，并且用子数组 P[2...n] 来产生前 n-1 个数的排列

• 接着，我们将 n 放在 P[2]上，并且用子数组 P[1]和 P[3...n]来产生前 n-1 个数的排列

• 然后，我们将 n 放在 P[3]上，并且用子数组 P[1...2]和 P[4...n]来产生前 n-1 个数的排列

• 重复上述过程直到我们将 n 放在 P[n]上，并且用子数组 P[1...n-1]来产生前 n-1 个数的排列

递归方程求解

公式法

• 对于下列形式的递归方程

• T(n) = aT(n/b) + f(n)

• 其中 a >= 1, b > 1 是常数，f(n)是一个渐进正函数，可以使用公式法(Master Method) 方便快捷地求得递归方程地解

• 将一个规模为 n 的问题划分成 a 个规模为 n/b 的子问题，其中 a 和 b 为正常数，分别递归地解决 a 个子问题，解每个子问题所需时间为 T(n/b)，划分原问题和合并子问题的解所需的时间由 f(n)决定

• 令 a >= 1 和 b > 1 是常数，f(n)是一个正函数，T(n)满足

• T(n) = aT(n/b) + f(n)

• 其中 n/b 表示[n/b]或者[n/b], 则 T(n)有如下三种情况的渐进界

• if f(n) = O(n^{log_ba-$\epsilon$}), for some constant $\epsilon$ > 0, then T(n) = $\Theta$(n^log_ba)

• if f(n) = $\Theta$(n^log_ba), then T(n) = $\Theta$(n^log_ba lgn)

• if f(n) = $\Omega$(n^{log_ba+$\epsilon$}), for some constant $\epsilon$ > 0, and if af(n/b) &\leq& cf(n) for some c < 1 and all sufficiently large n, then T(n) = $\Theta$(f(n))

案例

• T(n) = 9T(n/3) + n, a = 9, b = 3, f(n) = n, and n^log_ba = n^log₃9 = n²f(n) = O(n^{log_ba-$\epsilon$}) = O(n^log₃9-1)T(n) = $\Theta$(n²)

• T(n) = T(2n/3) + 1, a = 1, b = 3/2, f(n) = 1, and n^log_ba = n^log_3/21 = n⁰ = 1f(n) = $\Theta$(n^log_ba) = $\Theta$(1)T(n) = $\Theta$(lgn)

• T(n) = T(n-1) + n, f(n) = n, a = b = 1, 不可应用此方法