数据结构之递归

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

在谷歌搜索中由这样的彩蛋。

满足条件

1. 一个问题的解可以分解为几个子问题的解
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件

秘诀

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

案例

斐波那契数列

public class PrintFib {
    
    public static int fib(int num) {
        if(num == 1 || num == 2) {
            return 1;
        }else {
            return fib(num - 2) + fib(num - 1);
        }
    }
    
    public static void main(String[] args) {
        
        for(int i = 1;i <= 10;i++) {
            System.out.print(fib(i) + "\t");
        }    
    }    
}

汉诺塔

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

图片来源:https://www.zhihu.com/question/24385418

import java.util.Scanner;
 
public class Hanoi {
    static long s = 0;
 
    public static void main(String args[]) {
 
        int n = 0;
        System.out.println("请输入汉诺塔的层数:");
        Scanner console = new Scanner(System.in);
        n = console.nextInt();
        System.out.println("汉诺塔层数为" + n);
        System.out.println("移动方案为：");
        hanoi(n, 'a', 'b', 'c');
        System.out.println("需要移动次数：" + s);
 
    }
 
    static void hanoi(int n, char a, char b, char c) { //a为初始塔，b为中间塔，c为目标塔
        if (n == 1){  
            System.out.println("n=" + n + " " + a + "-->" + c);  
            s++;
        }
        else{  
            hanoi(n-1,a,c,b);
            System.out.println("n=" + n + " " + a + "-->" + c);  
            hanoi(n-1,b,a,c);  
            s++;
        }
    }
}