相关文章：
算法系列

• 前言
• 一、求5的阶乘
• 二、求1+2+3+4+...+10的和
• 三、求n阶乘的和
• 四、求斐波那契数列的第 N 项
• 五、兔子繁殖问题
• 六、青蛙跳台阶问题
• 七、求解汉诺塔问题

前言

递归，在数学与计算机科学中，是指在方法的定义中使用方法自身。也就是说，递归算法是一种直接或者间接调用自身方法的算法。简言之：在定义自身的同时又出现自身的直接或间接调用。

递归算法解决问题的特点：
1）递归就是方法里调用自身。
2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。
4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

下面题型主要是递归的典型示例，我将用递归与常规解法来解题进行对比，更加了解递归。

一、求5的阶乘

图解：

代码展示：（递归）

public class Test {    public static int fac(int n) { if (n == 1) {     return 1; } return n * fac(n-1);    } public static void main(String[] args) { int n = 5; System.out.println(fac(n));    }}

运行结果：

代码展示：(for循环)

public class Test {    public static void main(String[] args) { int n = 5; int ret = 1; for (int i = 1; i <= 5; i++) {     ret = i * ret; } System.out.println(ret);    }}

–

二、求1+2+3+4+…+10的和

代码展示：（递归）

public class Test {    public static int Sum(int n) { if (n == 1) {     return 1; } return n + Sum(n-1);    }    public static void main(String[] args) { int n = 10; System.out.println(Sum(n));    }}

运行结果：

代码展示：（for循环）

public class Test {    public static void main(String[] args) { int sum = 0; for (int i = 0; i <= 10; i++) {     sum += i; } System.out.println(sum);    }}

–

三、求n阶乘的和

经过前面两道题，这道题就变得很简单了。

代码展示： （递归）

public class Test {   public static long factorial(int n) {   获取相应数的阶乘方法if (n == 1) {    return 1;}return n * factorial(n-1);   }   public static long sum(int n) {    //求对应数的和的方法if (n == 1) {    return 1;}return factorial(n) + sum(n-1);   }    public static void main(String[] args) { System.out.println(sum(4));   //我这求的是前4个数的阶乘    }}

运行结果：

代码展示：（for循环）

import java.util.Scanner;public class Test {    public static void main(String[] args) { Scanner scan = new Scanner(System.in); long a = scan.nextInt(); long sum = 0; long s; for (int i = 1; i <= a; i++) {     s = 1;     for (int j = 1; j <= i; j++) {  s = s * j;     }     sum = sum +s; } System.out.println(sum);    }}

运行结果：

–

四、求斐波那契数列的第 N 项

斐波那契数列的第一个项和第二项都是1，所以在n=1或者n=2的情况下直接返回1。
n不等于1或2时，第n项斐波那契数列等于n-1项与n-2项的和，使用递归的方法。

1,1,2,3,5,8… 递推公式f(n) = f(n-1) + f(n-2)

代码展示：(递归)

import java.util.Scanner;public class Test {    public static int fib(int n) { if (n == 1 || n == 2) {     return 1; } return fib(n - 1) + fib(n - 2);    }    public static void main(String[] args) { Scanner scan = new Scanner(System.in); int a = scan.nextInt(); int ret = fib(a); System.out.println(ret);    }}

运行结果：

代码展示：（for循环）

import java.util.Scanner;public class Test {    public static int fib(int n) { if (n == 1 || n == 2) {     return 1; } int i = 1; int j = 1; int sum = 0; for (int m = 3; m <= n; m++) {    //从第三项开始每一项的数字为前两项之和     sum = i + j;     i = j;     j = sum; } return sum;    }    public static void main(String[] args) { Scanner scan = new Scanner(System.in); int a = scan.nextInt(); int ret = fib(a); System.out.println(ret);    }}

–

五、兔子繁殖问题

兔子繁殖其实就是斐波那契数列的例子

已知有一对兔子，每个月可以生一对兔子，而小兔子一个月后又可以生一对小兔子(比如:2月份出生的小兔子4月份可以生育)。也就是说，兔子的对数为：第一个月1对，第二个月2对，第三个月3对，第四个月5对…假设兔子的生育期为两年，且不死。那么问题来了，你能说出每个月的兔子数么?

代码展示：

import java.util.Scanner;public class Test {    public static int fib(int n) { if (n == 1 || n == 2) {     return 1; } return fib(n - 1) + fib(n - 2);    }    public static void main(String[] args) { System.out.print("请输入某个月："); Scanner scan = new Scanner(System.in); int a = scan.nextInt(); int ret = fib(a); System.out.println("这个月的兔子对数："+ret);    }}

运行结果：

–

六、青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法？

1个台阶：1 1种
2个台阶：1+1 2 2种
3个台阶：1+1+1 2+1 1+2 3种
4个台阶：1+1+1+1 1+2+1 2+2 1+1+2 2+1+1 5种
所以第n级台阶的跳法为（n-1）+（n-2）的和。

代码展示：

import java.util.Scanner;public class Test {   public static int fac(int n) {if (n ==1 || n == 2) {    return n;}return fac(n-1) + fac(n-2);   }    public static void main(String[] args) {Scanner scan = new Scanner(System.in);int num = scan.nextInt(); System.out.println(fac(num));    }}

运行结果：

七、求解汉诺塔问题

汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。
问应该如何操作？

问题分析：假设三根柱子分别为A B C 。将盘子从A上全部移动到C上。
1个盘子：A ->C 移动一次
2个盘子：A->B A->C B-.>C 移动三次
3个盘子：A->C A->B C->B A->C B->A B->C A->C 移动七次
观察发现：1个盘子移动次数为2；两个盘子次数为2^2 -1 ;三个盘子移动次数为2^3 -1;……64个盘子为2^64-1

图解：

代码展示：

public class Test {    public static void move(char pos1,char pos3) { System.out.println(pos1 + "->" + pos3);    }    public static void hanoi(int n,char pos1,char pos2,char pos3) { if (n==1) {     move(pos1,pos3);     return; } hanoi(n-1,pos1,pos3,pos2); move(pos1,pos3); hanoi(n-1,pos2,pos1,pos3);    }    public static void main(String[] args) { hanoi(3,'A','B','C'); System.out.println();    }}

运行结果：

共勉~