一、什么是递归？
递归：一个方法中又包含了本身。
通俗来说，递归就是自身中又包含了自己，是将一个原问题题分成若干子小问题，子问题与原问题的解法是一致的。
构成递归的两个必要条件 ：
- 要有递归出口，否则就会进入死循环。
- 将原问题划分为若干子问题，原问题要与子问题的解法一致。
解决递归问题的关键是要求出递推公式。
二、递归练习
1、按位输出一个整数
问题描述：将一个整数按位输出，例如:123 输出结果为：1 2 3
思路分析： 对于按位输出，首先要输出的是最高位，就是对该整数不断整除10，直到小于10，这就是递归出口，对于其他位我们可以输出对10取模，那么我们就可以使用递归来解决。
代码实现 ：
public static void printNum(int n){ if(n<10){ System.out.print(n+" "); return; } printNum(n/10); System.out.print(n%10+" "); } public static void main(String[] args) { printNum(123); }
运行结果：
2、递归求 N 的阶乘
思路分析：对于阶乘有一个特点，N的阶乘为为N*(N-1)！，例如：5!=5*4! ，递归的出口便是1的阶乘为1。
代码实现：
public static int factorial(int n){ if(n==1){ return 1; }else{ return n*factorial(n-1); } } public static void main(String[] args) { System.out.println(factorial(5)); }
运行结果：
3、返回的数字之和
题目描述： 输入一个非负整数，返回组成它的数字之和。
思路分析：对于本题，需要求出各个位的数字，然后进行相加，由于与顺序无关，就可以对数字整除10，直至小于10，得到递归出口，然后是对数字取模相加。
代码实现：
public static int countNum(int num){ if(num<10){ return num; }else{ return num%10+countNum(num/10); } } public static void main(String[] args) { System.out.println(countNum(125)); }
运行结果：
三、汉诺塔问题
汉诺塔问题：该问题是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个盘子。目标：把A杆上的金盘全部移到C杆上，
并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
针对该问题可以先归纳：
假设只有一个圆盘：直接A->C完成
假设有两个圆盘：
需要A->B,A->C,B->C
假设有三个圆盘：
需要A->C ，A->B ，C->B， A->C ，B->A ，B->C， A->C
可以总结出规律：如果只有n==1，则直接 A->C，这就是递归出口，否则先将n-1个圆盘利用C，从A->B,然后再将最底层的圆盘从 A->C，然后再将剩余的n-1，利用A,从B->C。
代码实现：
public static void hunNuoTa(int n,char pos1,char pos2,char pos3){ if(n==1){ move(pos1,pos3); return; } hunNuoTa(n-1,pos1,pos3,pos2); move(pos1,pos3); hunNuoTa(n-1,pos2,pos1,pos3); } public static void move(char pos1,char pos2){ System.out.print(pos1+"->"+pos2+" "); } public static void main(String[] args) { hunNuoTa(3,'A','B','C'); }
运行结果：
