第3章　递归与回溯法的编程实验

程序调用自身的编程技巧称为递归（recursion），是子程序在其定义或说明中直接或间接调用自身的一种方法。

首先，用视觉形式来说明递归。我们来看德罗斯特效应（Droste effect）：一张图片的某个部分与整张图片相同，如此产生无限循环。例如，图3-1就是德罗斯特效应的一个实例。

图　3-1

递归就是将一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，因此只需少量的程序代码就可描述出解题过程所需要的多次重复计算，使程序更为简洁和清晰。

在递归过程实现的时候，系统将每一层的返回点、局部变量等用栈来进行存储。调用递归时，当前层的返回点和局部变量入栈；回溯时，当前层的返回点和局部变量出栈。利用这种特性设计递归算法，程序就会变得十分简洁。需要注意的是，如果递归过程无法到达递归边界或递归次数过多，则会造成栈溢出。例如，设初始时n为大于0的自然数，对于函数，当n为偶数时，递归函数f(n)无法到达递归边界f(1)，程序也会因栈溢出而失败退出。

递归算法一般用于解决三类问题：

·函数的定义是递归的（如阶乘n!或Fibonacci函数）；

·数据的结构形式按递归定义（如二叉树的遍历、图的深度优先搜索）；

·问题的解法是递归的（如回溯法）。

回溯（backtracking）是一种穷举的搜索尝试方法。假定一个问题的解能够表示成n元组(x₁,x₂,…,x_n)，x_i∈S_i，n元组的子组(x₁,x₂,…,x_i)称为部分解，应满足一定的约束条件（i<n）。回溯法的基本思想是，若已有满足约束条件的部分解，添加x_i+1∈S_i+1，检查(x₁,x₂,…,x_i,x_i+1)是否满足约束条件，如果满足则继续添加x_i+2∈S_i+2；如果所有的x_i+1∈S_i+1都不能得到部分解，就去掉x_i，回溯到(x₁,x₂,…,x_i-1)，添加尚未考察过的x_i∈S_i，看其是否满足约束条件。如此反复，直至得到解或者证明无解。

采用递归方法求解回溯问题是递归算法的一个应用。回溯法从初始状态出发，运用题目给出的条件和规则，按照纵深搜索的顺序递归扩展所有可能情况，从中找出满足题意要求的解。所以，回溯法就是走不通就退回再走的技术，非常适合采用递归方法求解。

递归与回溯的综述如下。递归是一种算法结构。递归出现在程序的子程序中，形式上表现为直接或间接地自己调用自己。而回溯则是一种算法思想，它是以递归实现的。回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。