程序员诠释递归，Java高级算法视频教程

　　什么是递归

　　百度百科：程序调用自身的编程技巧称为递归（recursion）。

　　递归问题分析的核心

　　一个合法的递归定义包含两个部分：基础情况和递归部分。

　　分析一个递归问题就是列出递归定义表达式的过程。

　　上面那个电影院排数的问题表达式可以列为：

　　几个经典题目

　　斐波那契数列

　　斐波那契数列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次类推下去，你会发现，它后一个数等于前面两个数的和。在这个数列中的数字，就被称为斐波那契数。

　　递归思想：一个数等于前两个数的和。(这并不是废话，这是执行思路)

　　首先分析数列的递归表达式：

　　代码如下:

　　可以看到，递归写法简单优美，省去考虑很多边界条件的时间。当然，递归算法会保存很多的临时数据，类似于堆栈的过程，如果栈深太深，就会造成内存用尽，程序崩溃的现象。Java为每个线程分配了栈大小，如果栈大小溢出，就会报错，这时候还是选择递推好一点。

　　观察下面的执行过程也会发现，本程序并没有保存每次的运算结果，第三行的F(7)就执行了两次，下层的F(1),F(2)的次数更是指数级增长。这也是本程序的一个弊端。

　　斐波那契执行过程：

　　阶乘

　　递归思想：n!=n*(n-1)!(直接看公式吧)

　　首先分析数列的递归表达式：

　　代码如下:

　　执行过程如下：

　　倒序输出一个正整数

　　例如给出正整数n=12345，希望以各位数的逆序形式输出，即输出54321。

　　递归思想：首先输出这个数的个位数，然后再输出前面数字的个位数，直到之前没数字。

　　首先分析数列的递归表达式：

　　代码如下:

　　汉诺塔

　　超经典了的递归解决问题了：

　　法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

　　数学描述就是：

　　有三根杆子X，Y，Z。X杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至Y杆：

　　1.每次只能移动一个圆盘；

　　2.大盘不能叠在小盘上面。

　　递归思想：

　　1.将X杆上的n-1个圆盘都移到空闲的Z杆上，并且满足上面的所有条件

　　2.将X杆上的第n个圆盘移到Y上

　　3.剩下问题就是将Z杆上的n-1个圆盘移动到Y上了

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

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

　　2.将第n个圆盘移动到Y杆上

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

　　代码如下：

　　执行过程：

　　如果一秒钟移动一次，世界毁灭需要多长时间呢？5845.54亿年以上，而地球存在至今不过45亿年，地球现在还是很安全的。

　　排列问题

　　输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

　　递归思想：

　　假如针对abc的排列，可以分成(1)以a开头，加上bc的排列(2)以b开头，加上ac的排列(3)以c开头，加上ab的排列

　　本题用递归算法很巧妙，省去了用普通方法时保存数据状态的繁琐操作！