一、递归的思想
1. 递归分别表示递和归的两个动作，“ 函数递，函数归 ”。也就是说递归的本质是自己调用自己。
2. 函数递归要有两个必要的条件：
(1) 递归需要设置一个终止条件，以此来结束无限调用。
(2) 每一次的递归要无限趋近于这个条件。
如果不满足上面的这两个条件，函数递归就会无限地递归下去，直至栈溢出。栈溢出即表示栈区的内存被占满了。
如下图所示，当我们使用一个函数时，函数内的创建的局部变量都是放在栈区内存中存储的，如果无限递归下去不停止，就会导致栈区的内存超额。比如下面的 f 变量。
二、一些递归的题目
1. 递归求阶乘
程序清单1：
public class Test1 { public static void main(String[] args) { int n = 3; System.out.println(fac(n)); } public static int fac(int n){ if(n == 1){ return 1; }else{ return n * fac(n- 1); } } } //3*2*1 = 6
思想：
红色线条为递，绿色线条为归。
2. 递归求和
程序清单2：
public class Test2 { public static void main(String[] args) { int n = 10; System.out.println(fac(n)); } public static int fac(int n){ if(n==1){ return 1; }else{ return n + fac(n- 1); } } } //10+9+8+...+2+1 = 55
3. 递归顺序打印一个给定数字中各个位数
程序清单3：
public class Test3 { public static void main(String[] args) { int n = 1357; fac(n); } public static void fac(int n){ if(n/10 == 0) { System.out.print(n % 10+ " "); }else{ fac(n / 10); System.out.print(n % 10+ " "); } } } //输出 1 3 5 7
分析：
(1) 上面代码通过 n / 10 和 n % 10 来进行转换位数，这里不再赘述
(2) 这里递归的终止条件是 n / 10 == 0，也就是说，碰到给定数字的个位数的时候，就 “ 归 ”
4. 递归输出一个数中各个数字相加之和
程序清单4：
public class Test4 { public static void main(String[] args) { int n = 1357; System.out.println(fac(n)); } public static int fac(int n){ if(n/10 == 0) { return ( n % 10 ); }else{ return fac(n/10) + n % 10; } } } // 1+3+5+7 = 16
5. 斐波那契数列的实现
0 1 1 2 3 5 8 13 21 34 55 89…
斐波那契数列的特点：
(1) F(0) = 0，F(1) = 1，F(2) = 1
(2) 当 n >= 2，F(n) = F(n - 1) + F(n - 2)
特点1就是终止条件，特点2就是实现规律的公式
程序清单5（递归法）：
public class Test5 { public static void main(String[] args) { int n = 10; for (int i = 0; i <= n; i++) { System.out.println(fib(i)); } } public static int fib(int n){ if(n == 0){ return 0; } if(n==1 || n==2){ return 1; }else{ return fib(n-1)+ fib(n-2); } } } //输出 0 1 1 2 3 5 8 13 21 34 55
程序清单5（迭代法）：
public class Test5 { public static void main(String[] args) { int n = 10; fib(n); } public static void fib(int n){ int a = 0; int b = 1; for (int i = 0; i <= n; i++) { if(i==0 || i==1){ System.out.println(i); } else{ int c = a + b; a = b; b = c; System.out.println(c); } } } } //输出 0 1 1 2 3 5 8 13 21 34 55
分析思路：
总结
- 本人最近从 C 转到 Java，将递归又重新学了一遍，好处一在于巩固了算法，好处二在于熟悉新的代码风格，并增加了印象。其实不论是 C 还是 Java，实现的算法和逻辑都是相同的，只是语言不同，风格不同。
- 现在慢慢感受到了，语言只是工具，不论什么语言都是来解决问题的，语言不同只是语法层面上的不同，最重要还是要有解决问题的思想。
- 关于一些代码的细节部分没有赘述，比如函数内在的一些逻辑，比如递归求斐波那契数列为什么没有迭代法求出来更加高效。因为本篇博客旨在阐明递归的思想，读者可以从我给出的例子自我体会，只需要掌握每个问题的规律即可，没有必要深挖下去。
- 下一篇博客十七会分享使用递归来解决青蛙跳台阶和汉诺塔的问题。
Over. 谢谢观看哟~
