解读递归算法原理和效率( 二 ) _递归算法

递归思想：

将X杆上的n-1个圆盘都移到空闲的Z杆上，并且满足上面的所有条件
将X杆上的第n个圆盘移到Y上
剩下问题就是将Z杆上的n-1个圆盘移动到Y上了

公式描述有点麻烦，用语言描述下吧：

以Y杆为中介，将前n-1个圆盘从X杆挪到Z杆上(本身就是一个n-1的汉诺塔问题了！)
将第n个圆盘移动到Y杆上
以X杆为中介，将Z杆上的n-1个圆盘移到Y杆上(本身就是一个n-1的汉诺塔问题了！)

代码如下：
/** * 汉诺塔 * 有柱子 x z y，最终将x上的n个圆盘借助z移动到y上 * 递归思想： * 1.将x上的n-1个放入到z上，借助y * 2.将x上的n圆盘放到y上 * 3.将z上的n-1个圆盘放入y * @param n * @param from * @param tmp * @param to */void hanoi(int n,char from,char tmp,char to){ if (n>0) { hanoi(n - 1, from, to, tmp); System.out.println("take " + n + " from " + from + " to " + to); hanoi(n - 1, tmp, from, to); }}递归的效率还是拿斐波那契数列来做例子：
long Fib(int n){ if (n<=1) return n; return Fib(n-1)+Fib(n-2);}这段代码应该算是短小精悍（执行代码只有一行），直观清晰，而且非常符合许多程序员的代码美学，是如果用这段代码试试计算Fib(1000)我想就再也爽不起来了，它的运行时间也许会让你抓狂。
看来好看的代码未必中用，如果程序在效率不能接受那美观神马的就都是浮云了。如果简单分析一下程序的执行流，就会发现问题在哪，以计算Fibonacci(5)为例：

文章插图

从上图可以看出，在计算Fib(5)的过程中，Fib(1)计算了两次、Fib(2)计算了3次，Fib(3)计算了两次，本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显，以至于Fib(1000)已经无法再可接受的时间内算出。
我们当时使用的是简单的用定义来求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2) 。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2)，也就是说fib(n-2)调用了两次，同样的道理，调用f(n-2)时f(n-3)也调用了两次，而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。
由以上分析我们可以看到，递归在处理问题时要反复调用函数，这增大了它的空间和时间开销，所以在使用迭代可以很容易解决的问题中，使用递归虽然可以简化思维过程，但效率上并不合算。效率和开销问题是递归最大的缺点。
虽然有这样的缺点，但是递归的力量仍然是巨大而不可忽视的，因为有些问题使用迭代算法是很难甚至无法解决的。这时递归的作用就显示出来了。