关于递归算法设计的思考

前言

之前公司管理系统项目需要配合前端 VUE 实现动态路由，返回的数据结构是一个树形结构，但在数据库中存储的是平行的数据项。这个时候就需要在代码中去进行数据结构的组装。好久没思考这些问题，花了好些时间才搞定。这其中涉及到递归算法的实现，乘着周末深入的思考了下递归算法的设计，一点点拙见写下来做个笔记。

什么是递归？

对于 递归 其实我们并不陌生。还记得中学时代经常使用的 数学归纳法？，递归 其实并不是计算机科学独有的概念。实际上 数学归纳法 才是递归的理论基础。

先举个简单的栗子：求 n! 这里使用递归来求解。

int foo(int n) {
	if(n != 1) {
		return n*foo(n-1);
	}
	return 1;
	}

上面代码所表达的含义是：当 n 不等于 1 的时候。一直去调用 foo（n-1） 并且和传入的 n 相乘。在这里解释下递归调用的实现原理：我们知道计算机中函数的调用是使用栈的数据结构实现的，比如传入的 n 为 5 时，第一次执行 foo 方法，当执行到 foo(n-1),方法 foo 会被压入栈中。其实递归方法的出栈入栈和普通方法是一样的。唯一的区别是递归调用的是自身的代码。这里不妨把 foo 的每次调用称作 foo1,foo2 等等。那么这样就好理解了，当 foo 方法执行到 n==1 的时候，栈里面依次存放着 foo1,foo2,foo3,foo4,foo5。 此时 foo5 在栈顶,出栈执行。foo5 执行的时候 n==1，由代码可知，n==1，方法直接返回 1。接着 foo4 出栈，传入的 n 为 2，运算 2*1，然后 foo3,foo2,foo1 依次出栈，运算依次为：3*2,4*6 当最后一个方法 foo1 return 时计算，5*24，运行结束。

从这个过程中不难看出，递归是个不断下降的过程。层层调用自身，然后求值又是个上升的过程。从递归结束的出口返回值开始，层层向上求值。

从这个例子中还可以看出递归算法的两个重要特征，比如：

1. 不停调用自身
2. 有终止的条件，不然就成了死循环了

需要思考的问题是终止条件是如何确定的，以及他是怎么变化的。在上面的程序中是做 -1 操作。

何时考虑使用递归呢？

当定义是递归时

和上面求阶乘的例子类型一样。斐波那契数列 的定义就是递归的。直接看代码：

int Fib(int n) {
	if(n==1 || n==2) {
		return 1;
	}else {
		Fib(n-1)+Fib(n-2)
	}
}

斐波那契数列 ： 1,1,2,3,5 ...

当数据结构本身是递归时

最常见的比如链表的定义（这里讨论的是没有头节点的链表）：

class Node {
	private String data; //节点数据域
	private Node next; //指向下一个节点
}

当需要对链表数据域求和时,可以使用递归实现：

int SUM(Node node){
	if(node == null) {
		return 0;
	}else {
		return node.getData()+SUM(node.getNext());
	}
}

当问题需要用递归求解

这里详细讨论下汉诺塔算法的实现。

汉诺塔问题描述：有三个分别叫做 X，Y，Z 的塔座。在塔座 X 上有直径各不同，从小到大依次标号为：1，2，3...n 的盘片，现在要求把塔座 X 上的盘片移动到塔座 Z 上，按相同顺序叠放。移动时需要遵守规则：1.每次只能移动一个盘片。 2.盘片可以放在任意一个塔座上。 3.不能将较大的盘片放在较小的上面。

汉诺塔是典型的递归求解问题。光看描述不容易分析问题如何分解，不如在问题规模较小时，试着分析下解决方案。

当 X 塔座上只有一个盘片时：

X==>Z

当 X 塔座上有两个盘片时：

X1==>Y,X2==>Z

Y1==>Z

当 X 塔座上有三个盘片时：

X1==>Z,X2==>Y

Z==>Y,X==>Z

Y1==>X,Y2==>Z

X==>Z

先给出递归算法，这个算法将打印出移动的步骤。

void Hanoi(int n,String X,String Y,String Z) {
	if(n == 1) {
	System.out.println("将第"+n+"个盘片从"+X+"移到"+Z); //X==>Z
	}else {
	Hanoi(n-1,X,Z,Y);
	System.out.println("将第"+n+"个盘片从"+X+"移到"+Z); //X==>Z
	Hanoi(n-1,Y,X,Z);
	}
}

汉诺塔的基本要求是要把最大的放在最下面,所以当 X 塔座上的盘片数量大于 1 时，我们首先要把 X 塔座上，1至n-1 的盘片放到 Y 上，于是我们可以忽略 X 最下面的盘片，把 Y 当做 Z，Z 当做 Y，这样问题回到了，当 X 有 n-1 个盘片，如何移动到 Z 的情形。记住这个时候的 Z 是 Y。 现在我们已经做到了把 X 上 1至n-1 的盘片放到了 Y 上。别忘了 X 上还有一个我们忽略的最大盘片。

好，现在把 X 最大盘片放到 Z，这个时候 X 没有盘片，Y 有 1至n-1 的盘片，现在我们忽略 Z 上的最大盘片。将 Y 当做 X，X 当做 Y。问题又回到了 X 上有 n-1 个盘片如何移动到 Z 的情形。

再看上面给出的代码。当 n==1 时，直接把 X 移到 Z，否则，将 Y 当做 Z，Z 当做 Y，将 1至n-1 盘片移到 Y 上。这个时候取出 X 最大盘片放到 Z。再把 X 当 Y，Y 当做 X，继续递归。直到 n==1，移动成功！其实不难发现当执行到第二个 System.out.println("将第"+n+"个盘片从"+X+"移到"+Z); 时。已经完成了将 X 的最大盘片移到 Z 的目标。汉诺塔的层数减一。问题回到了最初的情形，只不过，盘片在 Y 上，不在 X 上。但是这不妨碍调用 Hanoi 方法。实际上问题的关键在于，X，Y，Z 三个塔座没有区别是一样的。还有一轮操作完之后，只是把最下面的盘片放到了 Z，这个时候问题的规模就减一了。

如何设计递归算法？

找出递归结束条件

上文总结的递归特征中，有一条说明了递归必须要有终止条件。比如求阶乘，斐波那契数列以及汉诺塔问题，它们在递归调用时表示问题规模的 n 一直在递减，直到达到递归结束条件 n==1。实际上，递归条件不一定是这种通过递减来达到结束条件判断值的，比如在构造树形结构的时候，可以通过判断数据项的 isLeaf 字段是否为 true 来决定是否退出递归。有一点可以肯定的是，递归退出条件一定隐藏在初次调用传入方法的参数中以及一切在方法运行时可以访问的状态。

找出循环体

这是一个比较难的问题，对于类似数学定义问题，循环体往往就是定义问题的那几句话，比如斐波那契数列的定义：当0<n<3时，Fib=1，当n>2时，Fib(n)=Fib(n-1)+Fib(n-2)。当为递归数据结构设计算法时，循环体则是访问递归结构的指令。比如遍历链表时：

void foo(node) {
	if(node != null) {
		foo(node.getNext());
	}else {
		return;
	}
}

但是像汉诺塔这类问题，直观上没办法直接看出递归的特征。个人经验则是在较小问题规模上，进行演算。发现递归特征。

小结

递归程序设计本身是比较难以理解和掌握的，通过简单的理论学习无法熟练运用，只有不断的解决问题才会熟能生巧。