计算机科学 A 复习：Unit 10 – 递归 Recursion

本单元要介绍的内容是「Recursion 递归」，这是一种把「大问题」拆解成若干个「小问题」的算法。具体的说，就是让 Method 调用自己从而达到循环的效果。

听起来有一点点抽象，但是没关系，因为当前的AP考纲并不要求我们自己动手写出递归的代码。只要能根据输入值推算输出值就基本能拿到这部分的分数。接下来我们会看到几个递归算法的例子，只需要掌握这些例题的解法就基本上达到了AP考试的要求。

U10.1 Recursion 递归

「Recursion 递归」本质上就是写作一个会自己调用自己，从而一步一步拆解算式最终得到结果的算法。这种算法在自己调用自己的过程中形成了类似循环的效果，因此在程序写作的时候需要根据数据的实际情况、使用判断语句来触发对应的程序反应。

下面用求某个数字的阶乘的例子来详细解释：

public class Main {
	public static void main (String args[]) {
		System.out.println(fact(3));//测试：求 3 的阶乘
	}
	
	static int fact (int x) {//求x的阶乘
		
		if(x == 1 || x == 0) { // 1和0的阶乘都是 1
			return 1;
		}
		
		if(x > 1) { 
			return (x * fact(x - 1));
		}
		
		return -1;
	}
}

上面的例子中，我们给 fact method 传入了一个大于等于0的整数，然后在这个 method 里使用递归算法计算并返回被传入的整数的阶乘。

例如，在测试输出语句填入的数值是 3 ，也就是意图求得 3 的阶乘。3的阶乘 = 3 * 2 * 1 = 6 。（已知1和0的阶乘都是1）

从使用递归算法的角度来说，把「大问题」拆解成「小问题」，递归算法使用了判断语句来判断不同情况下的处理措施 ——

如果传入的数字本身就是1或0，那么就不需要继续求解，因为这两个数字的阶乘是已知的数值，可以直接返回1 。

但如果传入的数字大于 1，就需要拆项，也就是把第一次传入的数字拆解开，方便计算。例如，3就可以被拆解成 3 * 2！，而 3 * 2！又可以被拆解成 3 * 2 * 1，最终就可以计算得到3的阶乘的答案：6。（感叹号是阶乘符号，代表某个数字的阶乘。前文的 2！就是2的阶乘，2！= 2 * 1 = 2）

而在程序中进行拆项也很简单，这里用 x 代表传入的等待求阶乘值的数字，只需要返回「 x * fact ( x – 1 )」就可以。例如，如果首次传入的数字是 3 ，那么电脑判断 3 是大于 1 的，因此返回「 3 * fact ( 3 – 1 )」。这里就是在 fact method 内又让 fact 自己调用了自己，因此程序需要再计算「 fact ( 3 – 1 )」的数值，然后把这个数值乘前面的 3 。而「 fact ( 3 – 1 )」= 「 fact ( 2 )」，2也是大于 1的，所以第二次调用的时候又会需要返回「 2 * fact ( 2 – 1 )」。

已知「fact (1)」回返回 1，所以整个计算过程后得到 3 * 2 * 1 = 6 。拆解过程的草稿如下：

计算过程中，只要数值大于 1 ，判断语句就选择启动「我调用我自己」的情况；否则会返回「1」来终止这次递归计算。从术语上来说，「我调用我自己」的情况叫做「Recursive Call」；「终止递归计算」的情况则被称为「Base Case」。任何递归算法必须至少拥有一个「Recursive Call」和一个「Base Case」。

（至此，你可以尝试完成「练习」中的 2008-20）

U10.2 Recursive Searching and Sorting

搜索是递归算法常用的场景之一。但本单元并不涉及自己动手写代码，所以只要学会了上面的拆解求结论数值就可以完成考试题目。

总结

这个单元内容很少，且并没有涉及新的 Java 语法规则。这标志着在AP CSA课程的最后，我们已经开始接触更复杂的算法了。

练习

2008-20