关于递归算法设计的思考

正文

请到「今天看啥」查看全文

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

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

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.不能将较大的盘片放在较小的上面。

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

请到「今天看啥」查看全文