目录

递归

1.递归求N 的阶乘和递归求1+2+3+4······+n

2.按顺序打印一个数字的每一位

3.斐波那契数列和青蛙跳台阶问题

4.汉诺塔问题

递归

递归，简单来说，就是方法自己调用自己的过程，那要怎么样去实现递归呢？

首先，我们需要去根据条件，推导出一个递推公式，同时还需要有一个趋近于终止的条件，不能让他无限的调用自己，下面我们通过一些简单的例子来更加的了解递归。

1.递归求N 的阶乘和递归求1+2+3+4······+n

实现代码：

//    递归求n!
 public static int fac(int n) {
        if (n == 1){
            return 1;
        } else {
            return n * fac(n-1);
        }
    }


//       实现代码: 递归求 1 + 2 + 3 + ... + 10
    public static int sum(int n) {
        if (n == 1){
            return 1;
        } else {
            return n + sum(n - 1);
        }
    }

这两题类似也挺好理解的

2.按顺序打印一个数字的每一位

实现代码：

 public static void print(int n) {
        if (n <= 9){
            System.out.print(n + " ");
        } else {
            print(n / 10);
            System.out.print(n % 10 + " ");
        }
    }

这题举个例子 就拿1092，题目要求的意思是最后要得到 1 0 9 2这四个数字

而怎么去获得者四个数字呢？就需要我们 不断地拿n去/10 和%10 ，就可以打印这个数的每一位

 下面对这道题进行扩展

 写一个递归方法，输入一个非负整数，返回组成它的数字之和.

实现代码：

public static int sumPrint(int n){
        if (n <= 9){
            return n;
        } else {
            return sumPrint(n / 10) + n % 10;
        }
    }

3.斐波那契数列和青蛙跳台阶问题

青蛙跳台阶 ：青蛙每次可以跳一层或者两层，求跳到第n层有多少种方法

通过找规律发现，青蛙跳台阶和斐波那契数列一样，当n == 1 或者n ==  2的时候，得到的值为1 当n >=3 的 时候每个数等于前两个数的和

实现代码

public static int fb(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return fb(n - 2) + fb(n - 1);
        }
    }

4.汉诺塔问题

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

当n == 1 的时候 我们只需要将A上的盘子移到C即可

 当n == 2 的时候需要将第一个放到B上，再把第二个放到C上，最后将B上的放到C上即可 完全移到C上共需要三步

 通过如图对应的移动我们发现需要

移动方式  A-->C A-->B C-->B A-->C B-->A B-->C A-->C

我们发现 移动的次数是2的n次方- 1，同时当n>1的时候，我们每次需要把前n-1个盘子通过C中转移到B上，在将最下面的移到c上后，将B上的通过A中转移到C上，那么我们就有了如下的代码

// 显示移动路径
    public static void move(char pos1, char pos2) {
        System.out.print( pos1 + "-->" + pos2 + " ");
    }

    /**
     *
     * @param n  移动多少盘子
     * @param pos1   起始位置
     * @param pos2   中转位置
     * @param pos3   结束位置
     */
    public static void han(int n , char pos1, char pos2, char pos3){
        if (n == 1) {
            move(pos1,pos3);
        } else {
            //先把前 n - 1个盘子移到b上 利用c
            han(n - 1, pos1, pos3, pos2);
            move(pos1,pos3);
            //把b的盘子移到c上面
            han(n - 1, pos2, pos1, pos3);

        }
    }