递归算法——斐波那契数列、汉诺塔问题和二叉树的Java实现

使用递归算法的三个条件递归的应用程序示例1、斐波那契数列2、汉诺塔问题3、二叉树 编程语言中，函数直接或间接调用函数本身，则该函数称为递归函数。程序调用自身的编程技巧称为递归（ recursion）。递归通常是把一个大问题转化成为与大问题解决方法相似的小问题来解决，一般递归需要有 边界条件、 递归前进段和 递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

使用递归算法的三个条件

一个问题可以分解为几个子问题分解形成的子问题，除了数据规模不同，求解思路与原问题相同存在递归终止的条件

递归的应用

递归算法一般用于解决三类问题：

数据的定义是按递归定义的 如：斐波那契数列（Fibonacci sequence）问题解法按递归算法实现 如：汉诺塔问题（Hanoi）数据的结构形式是按递归定义的 如：二叉树、广义表等

程序示例

1、斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，是这样一组数列：1、1、2、3、5、8、13、21、34、……从这个数列的第3项开始，每一项都等于前两项数字的和。

for (int i = 1;i < 10;i++){ System.out.printf("%4d",fibonacci(i)); } //结果为： 1 1 2 3 5 8 13 21 34 //f(n) = f(n - 1) + f(n - 2) static int fibonacci(int nums){ if (nums < 0){ return 1; }else if (nums < 3){ return 1; }else return fibonacci(nums - 1) + fibonacci(nums - 2); }

2、汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。 【百度百科】

思路： 【注：start为圆盘开始时的位置，mid 为圆盘暂时存放的位置，last 为圆盘最终需要到达的位置】

当圆盘个数为1时，可以直接从 start 移动到 last当圆盘个数为n时，需要把（n - 1）个圆盘移动到 mid最后把剩下的圆盘移动到 last hanoi("A","B","C",3); static void hanoi(String start,String mid,String last,int n){ if(n == 1){ System.out.println(start+"------>"+last); }else{ //把 n - 1 个圆盘移动到过渡位置 hanoi(start,last,mid,n-1); //把最底层的圆盘移动到最后的位置 hanoi(start,mid,last,1); //把在过渡位置的 n - 1 个圆盘移动到最终的位置 hanoi(mid,start,last,n-1); } }

结果： 动画演示

3、二叉树

见前篇 链接: 二叉树遍历——Java的代码实现.