算法递归程序设计

发表于   |   分类于   |     |   阅读次数

学习目标

  • 递归的概念及用途。
  • 递归算法的设计方法。
  • 递归算法的执行过程。
  • 递归算法与迭代算法的关系。

引言

著名的八皇后问题：在棋盘上放置8个皇后，使其中任意两个都不同行、不同列、不在一条对角线上，如下图所示：
eightqueens

解决这个问题的方法——递归

递归的概念

递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。递归算法，其实说白了，就是程序的自身调用。它表现在一段程序中往往会遇到调用自身的那样一种coding策略，这样我们就可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁非常直观的代码形势，从而使我们的编码大大简化，然而递归的思维确实很我们的常规思维相逆的，我们通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。这样我们就能看到我们会用很少的语句解决了非常大的问题，所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。

递归的定义

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。

直接递归

1
2
3
4
fun_a()
{  … 
 fun_a()  …
}

间接递归

1
2
3
4
5
6
7
8
9
fun_a()
{  …  
    fun_b()  
…}

fun_b()
{  …  
    fun_a() 
…}

递归分类

  • 问题的定义是递归的
    例如：阶乘函数的定义
    1
    2
    3
            1               当n=0时  
    n！= 
            n*(n-1)！       当n>0时
1
2
factorial(0) = 1;
factorial(n) = n*factorial(n-1);

代码呈现：

1
2
3
4
5
6
public int factorial(int n) {
    if(n == 1)
        return 1;
    else
      return n * factorial(n - 1);
}
  • 问题的解法存在自调用
    例如：折半查找算法
    折半查找算法

折半查找递归算法

1
2
3
4
5
6
7
8
9
10
public static int bSearch(int[] a, int x, int low, int high) {
	int mid;
	if(low > high) return -1; 		            //查找不成功
	mid = (low + high) / 2;
	if(x == a[mid]) return mid; 			    //查找成功
	else if(x < a[mid])
		return bSearch(a, x, low, mid - 1); 	//在上半区查找
	else
		return bSearch(a, x, mid + 1, high); 	//在下半区查找
}

测试主函数设计如下：

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
	int[] a = {1, 3, 4, 5, 17, 18, 31, 33};
	int x = 17;
	int bn;
	bn = bSearch(a, x, 0, 7);
	if(bn == -1) 
		System.out.println("x不在数组a中");
	else
		System.out.println("x在数组a中，下标为" + bn);	
}

递归模型

递归模型反映一个递归问题的递归结构。一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定递归到何时为止，后者确定递归的方式。

递归出口的一般格式为：
f(s0)=m0；这里的s0与m0均为常量，有的递归问题可能有几个递归出口。

递归体的一般格式为：
f(s)=g(f(s1), f(s2),……, f(sn),c1, c2,……，cm)
这里的s是一个递归“大问题”，s1，s2，……，sn是递归“小问题”，c1，c2，……，cm是若干个可以直接（用非递归方法）解决的问题，g是一个非递归函数，反映了递归问题的结构。

例如，阶乘函数
阶乘函数

递归的执行过程

实际上，递归是把一个不能或不好直接求解的“大问题”转化为一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每一个“小问题”都可以直接解决（此时分解到递归出口）。

递归过程和运行时栈

递归函数的执行过程具有三个特点：

  1. 函数名相同；
  2. 不断地自调用；
  3. 最后被调用的函数要最先被返回。
    系统用于保存递归函数调用信息的堆栈称作运行时栈。
    每一层递归调用所需保存的信息构成运行时栈的一个工作记录
    栈顶的工作记录保存的是当前调用函数的信息，所以栈顶的工作记录也称为活动记录。

Computing Factorial

1
2
3
4
5
6
7
factorial(3) = 3 * factorial(2) 
           = 3 * (2 * factorial(1)) 
           = 3 * ( 2 * (1 * factorial(0))) 
           = 3 * ( 2 * ( 1 * 1))) 
           = 3 * ( 2 * 1) 
           = 3 * 2 
           = 6

Trace Recursive factorial

Trace Recursive factorial

factorial(4) Stack Trace

factorial(4) Stack Trace

Fibonacci 数

Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89…
indices: 0 1 2 3 4 5 6 7 8 9 10 11
fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index -1) + fib(index -2); index >=2

fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + fib(1) = (1 + 0) +fib(1) = 1 + fib(1) = 1 + 1 = 2

1
2
3
4
5
6
public static int Fibonacci(int n){
    if (n <= 1)  
        return n;  
    else  
        return Fibonacci(n-1) + Fibonacci(n-2);  
}

图形讲解如下：

递归算法的设计方法

适宜于用递归算法求解的问题的充分必要条件是：

  • 问题具有某种可借用的类同自身的子问题描述的性质。
  • 某一有限步的子问题（也称作本原问题）有直接的解存在。

当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是：

  • 把对原问题的求解表示成对子问题求解的形式。
  • 设计递归出口。

例：一条信息打印n次。
把这个问题分解成两个子问题：打印一次和打印n-1次。第二个问题和原始问题相同，只是规模小了。递归出口时 n==0. 

1
2
3
4
5
6
public static void nPrintln(String message, int times) {
    if (times >= 1) {
        System.out.println(message);
        nPrintln(message, times - 1);
    } // The base case is times == 0
}

例：回文序列

1
2
3
4
5
6
7
8
public static boolean isPalindrome(String s) {
	if (s.length() <= 1) // Base case
		return true;
	else if (s.charAt(0) != s.charAt(s.length() - 1)) // Base case
		return false;
	else
		return isPalindrome(s.substring(1, s.length() - 1));
}

输入”abcba”—返回true

递归辅助方法

前面的例子 isPalindrome 效率差，原因是它每次递归调用都会创建一个新的字符串。可以用辅助方法改进之:

1
2
3
4
5
6
7
8
9
10
11
12
public static boolean isPalindrome(String s) {
	return isPalindrome(s, 0, s.length() - 1);
}

public static boolean isPalindrome(String s, int low, int high) {
	if (high <= low) // Base case
		return true;
	else if (s.charAt(low) != s.charAt(high)) // Base case
		return false;
	else
		return isPalindrome(s, low + 1, high - 1);
}

递归技术的关键问题

  • 为防止递归的无休止调用，在递归函数中要及时返回，这就是结束条件的作用。在所有的递归函数中都有一个终止递归的条件判断。
  • 递归函数可以简化程序，但一般不能提高程序的执行效率。

案例一：文件夹大小

前面的问题也可以不用递归就解决，但是有些问题不用递归很难解决。比如：统计文件夹的大小问题，它是文件夹下所有文件大小的总和，而一个文件夹有可能包括子文件夹，假设文件夹结构如下：

文件夹大小可以递归地定义为:

案例二 ：汉诺塔问题的递归求解过程

汉诺塔(Tower of Hanoi)问题的解法：
如果 n = 1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步：
① 用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移到 B 柱上：
② 将 A 柱上最后一个盘子直接移到 C 柱上；
③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移到 C 柱上。

根据以上的分析，不难写出程序：

1
2
3
4
5
6
7
8
9
public static void Hanoi(int n, char A, char B, char C) {
    if (n == 1) { //end condition
        move(A, C); //‘move’ can be defined to be a print function
    } else {
        Hanoi(n-1, A, C, B); //move sub [n-1] pans from A to B
        move(A, C); //move the bottom(max) pan to C
        Hanoi(n-1, B, A, C); //move sub [n-1] pans from B to C
    }
}

案例三：分形

分形是一种几何图形，它划分成的部分都和整体图形相同，只是规模更小。介绍其中一种 Sierpinski 三角

Sierpinski Triangle

  1. 开始第0层是一个等边三角形，如图 (a)。
  2. 连接第0层每个边的中点得到第一层Sierpinski 三角，如图(b)。
  3. 中间的三角形不考虑，把其余的三个三角形的中点相连，得到第2层的Sierpinski 三角，如图(c)。
  4. 递归地重复这个过程，得到第3、4等等Sierpinski 三角，如图(d)。

Sierpinski Triangle Solution

案例四：八皇后

eightqueens

参考资料

递归算法详解

热评文章