递归

递归的算法思想

• 基本思想

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

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

  • 找到问题的初始条件（递归出口），即当问题规模小到某个值时，该问题变得很简单，能够直接求解
  • 设计一个策略，用于将一个问题划分为一个或多个一步步接近递归出口的相似的规模更小的子问题
  • 将所解决的各个小问题的解组合起来，即可得到原问题的解

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

• 如何使定义的问题规模逐步缩小，而且始终保持同一问题类型？
• 每个递归求解的问题规模如何缩小？
• 多大规模的问题可作为递归出口？
• 随着问题规模的缩小，能到达递归出口吗？

递归设计实例

1. 计算 f(n) = 2ⁿ

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

Program
f(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柱

   Hanoi(n, A, B, C)
   if n=1 then move(1, A, C)
   else
   Hanoi(n-1, A, C, B)
   move(1, A, C)
   move(n-1, B, A, C)

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

3. Selection sort

• 基本思想

  • 把所有牌摊开，放在桌上，伸出左手，开始为空，准备拿牌
  • 将桌上最小额牌拾起，并把它插到左手所握牌的最右边
  • 重复上一步，直到桌上的所有牌都拿到你的左手上，此时左手上所握得牌便是排好序的牌

  SelectionSort(i)
  if i >= n then return 0
  else
  k = i
  for j <- i+1 to n do
  if A[j] < A[k] then
  k <- j
  if k != i then A[i] <-> A[k]
  SelectionSort(i+1)

T(n) = T(n-1) + n
T(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 放到每个排列的开头

      GeneratingPerm1()
      	for j <- 1 to n do
      		P[j] <- j
      	Perm1()
    
      Perm1(m)
      	if m = n then output P[1...n]
      	else
      		for j <- m to n do
      			P[j] <-> P[m]
      			Perm1(m+1)
      			P[j] <-> P[m]
    

    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 个数的排列

    GeneratingPerm2()
    	for j<-1 to n do
    		p[j]<-0
    		Perm2(n)
  
    Perm2(m)
    	if m = 0 then ouput P[1 ... n]
    	else
    		for j<-1 to n do
    			if P[j]=0 then
    				P[j]<-m
    				Perm2(m-1)
    				P[j]<-0
  

递归方程求解

公式法

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

  • 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)有如下三种情况的渐进界
  1. if f(n) = O(n^{log_ba- $\varepsilon$}), for some constant $\varepsilon$ > 0, then T(n) = $\Theta$(n^log_ba)
  2. if f(n) = $\Theta$(n^log_ba), then T(n) = $\Theta$(n^log_ba lgn)
  3. if f(n) = $\Omega$(n^{log_ba+ $\varepsilon$}), for some constant $\varepsilon$ > 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- $\varepsilon$}) = 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⁰ = 1
  f(n) = $\Theta$(n^log_ba) = $\Theta$(1)
  T(n) = $\Theta$(lgn)

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