递归

定义：在定义自身的过程中又直接或间接调用自身的一种算法。

组成元素：
   1.递归调用
   2.递归终止条件

适用范围：
   1.一个问题可被分解为若干层简单的子问题
   2.子问题与其上一层问题解决方法一致
   3.外层问题的解决依赖子问题的解决

范例：Fibonacci数列
1.Fibonacci类

 1 /**
 2  * @Description: 斐波那契数列：
 3  * 1,1,2,3,5,8,13,21
 4  * F(n) = F(n-1) + F(n-2)
 5  * @author Ivy
 6  */
 7 public class Fibonacci {
 8 
 9     /**
10      *
11      * @Description: 计算F(n)
12      * @param n 月份数
13      * @return F(n) 兔子的总对数
14      */
15     public int F(int n) {
16         if (n < 1) {
17             return 0;
18         } else if (n == 1 || n == 2) {
19             return 1;
20         } else {
21             return F(n-1) + F(n-2);
22         }
23     }
24     
25 }

2.测试类

 1 public class FibonacciTest {
 2 
 3     public static void main(String[] args) {
 4 
 5         Fibonacci fibonacci = new Fibonacci();
 6         int n = 8;
 7         System.out.println("月数：" + n + ",兔子的对数：" + fibonacci.F(n));
 8         
 9     }
10 
11 }

范例：用递归计算n!
1.阶乘类 - Factorial

 1 /**
 2  * @Description: 用递归计算n!
 3  * @author Ivy
 4  */
 5 public class Factorial {
 6 
 7     public int recur(int n){
 8         if (n == 0) {
 9             return 1;
10         } else {
11             return n*recur(n - 1);
12         }
13     }
14     
15 }

2.测试类

 1 public class FactorialTest {
 2 
 3     public static void main(String[] args) {
 4         Factorial factorial = new Factorial();
 5         int n = 4;
 6         System.out.println(n + "!:" + factorial.recur(n));
 7 
 8     }
 9 
10 }