四、斐波那契数列

接触过C语言的同学很可能就知道什么是费波纳切数列了，因为往往做练习题的时候它就会出现，它也是递归的典型应用。

菲波那切数列长这个样子：{1 1 2 3 5 8 13 21 34 55..... n }

数学好的同学可能很容易就找到规律了：前两项之和等于第三项

例如：

1 + 1 = 2
    2 + 3 = 5
    13 + 21 = 34

如果让我们求出第n项是多少，那么我们就可以很简单写出对应的递归表达式了：Z = (n-2) + (n-1)

递归出口在本题目是需要有两个的，因为它是前两项加起来才得出第三项的值

同样地，那么我们的递归出口可以写成这样：if(n==1) retrun 1 if(n==2) return 2

下面就来看一下完整的代码吧：

public static void main(String[] args) {
        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);
        int fibonacci = fibonacci(10);
        System.out.println("公众号：Java3y：" + fibonacci);
    }
    public static int fibonacci(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        } else {
            return (fibonacci(n - 1) + fibonacci(n - 2));
        }
    }

五、汉诺塔算法

图片来源百度百科：

玩汉诺塔的规则很简单：

• 有三根柱子，原始装满大小不一的盘子的柱子我们称为A，还有两根空的柱子，我们分别称为B和C(任选)
  
• 最终的目的就是将A柱子的盘子全部移到C柱子中
  

• • 移动的时候有个规则：一次只能移动一个盘子，小的盘子不能在大的盘子上面(反过来：大的盘子不能在小的盘子上面)
    

我们下面就来玩一下：

• 只有一个盘子：
  

• • 将A柱子的盘子直接移动到C柱子中
    
  • 完成游戏
    

• 只有两个盘子：
  

• • 将A柱子上的小盘子移动到B柱子中
    
  • 将A柱子上的大盘子移动到C柱子中
    
  • 最后将在B柱子的小盘子移动到C柱子大盘子中
    
  • 完成游戏
    

• 只有三个盘子：
  

• • 将A柱子小的盘子移动到C柱子中
    
  • 将A柱子上的中盘子移动到B柱子中
    
  • 将C柱子小盘子移动到B柱子中盘子中
    
  • 将A柱子的大盘子移动到C柱子中
    
  • 将B柱子的小盘子移动到A柱子中
    
  • 将B柱子的中盘子移动到C柱子中
    
  • 最后将A柱子的小盘子移动到C柱子中
    
  • 完成游戏
    

…………………..

从前三次玩法中我们就可以发现的规律：

• 想要将最大的盘子移动到C柱子，就必须将其余的盘子移到B柱子处(借助B柱子将最大盘子移动到C柱子中[除了最大盘子，将所有盘子移动到B柱子中])[递归表达式]
  
• 当C柱子有了最大盘子时，所有的盘子在B柱子。现在的目的就是借助A柱子将B柱子的盘子都放到C柱子中(和上面是一样的，已经发生递归了)
  
• 当只有一个盘子时，就可以直接移动到C柱子了(递归出口)
  

• • A柱子称之为起始柱子，B柱子称之为中转柱子，C柱子称之为目标柱子
    
  • 从上面的描述我们可以发现，起始柱子、中转柱子它们的角色是会变的（A柱子开始是起始柱子，第二轮后就变成了中转柱子了。B柱子开始是目标柱子，第二轮后就变成了起始柱子。总之，起始柱子、中转柱子的角色是不停切换的)
    

简单来说就分成三步：

1. 把 n-1 号盘子移动到中转柱子
   
2. 把最大盘子从起点移到目标柱子
   
3. 把中转柱子的n-1号盘子也移到目标柱子
   

那么就可以写代码测试一下了(回看上面玩的过程)：

public static void main(String[] args) {
        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);
        //int fibonacci = fibonacci(10);
        hanoi(3, 'A', 'B', 'C');
        System.out.println("公众号：Java3y" );
    }
    /**
     * 汉诺塔
     * @param n n个盘子
     * @param start 起始柱子
     * @param transfer 中转柱子
     * @param target 目标柱子
     */
    public static void hanoi(int n, char start, char transfer, char target) {
        //只有一个盘子，直接搬到目标柱子
        if (n == 1) {
            System.out.println(start + "---->" + target);
        } else {
            //起始柱子借助目标柱子将盘子都移动到中转柱子中(除了最大的盘子)
            hanoi(n - 1, start, target, transfer);
            System.out.println(start + "---->" + target);
            //中转柱子借助起始柱子将盘子都移动到目标柱子中
            hanoi(n - 1, transfer, start, target);
        }
    }

我们来测试一下看写得对不对：

参考资料：

• https://www.zhihu.com/question/24385418
  

六、总结

递归的确是一个比较难理解的东西，好几次都把我绕进去了….

要使用递归首先要知道两件事：

• 递归出口(终止递归的条件)
  
• 递归表达式(规律)
  

在递归中常常用”整体“的思想，在汉诺塔例子中也不例外：将最大盘的盘子看成1，上面的盘子看成一个整体。那么我们在演算的时候就很清晰了：将”整体“搬到B柱子，将最大的盘子搬到C柱子，最后将B柱子的盘子搬到C柱子中

因为我们人脑无法演算那么多的步骤，递归是用计算机来干的，只要我们找到了递归表达式和递归出口就要相信计算机能帮我们搞掂。

在编程语言中，递归的本质是方法自己调用自己，只是参数不一样罢了。

最后，我们来看一下如果是5个盘子，要运多少次才能运完：