关于递归算法设计的思考

前言

之前公司管理系统项目需要配合前端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;
	}
}

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

小结

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