递归算法的一些简单的实例

 1 　　/***
 2      * 递归求和  1+2+3+...+n
 3      * @param n 输入的数值
 4      * @return
 5      */
 6     public static int recursionSum(int n){
 7         
 8         if(n>0){
 9             return n + recursionSum(n);
10         }else{
11             return 0;
12         }
13     }
14     
15     /***
16      * 递归阶乘  n! = n*(n-1)*(n-2)*...*1
17      * @param n 需要求取阶乘的数值
18      * @return
19      */
20     public static int recursionMulity(int n){
21         
22         if(n == 1){
23             return 1;
24         }
25         return n * recursionMulity(n-1);
26     }
27     
28     /***
29      * 题意：一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。
30      * 这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
31      * 
32      * 分析：第七天后该人只有2只鸭子，记每天的鸭子数量为num，则之前每天的鸭子总数为当天后一天的(num+1)*2只，当天卖掉的鸭子个数为(num/2)+1只
33      * 
34      * 算法步骤：
35      * 1) 令num等于2，n等于7；
36      * 2) 计算前一天的总鸭子数量num = (num + 1) * 2；
37      * 3) 计算并输出第n天卖掉的鸭子数量；
38      * 4) 将n减去1，判断n是否大于0，若是，则输出总鸭子数量num，否则，递归调用函数继续进行计算。
39      *
40      * @param num 最后一天剩余的鸭子的数量
41      * @param counter 村庄的个数
42      * @return 计算出的sum的和
43      */
44     public static int duck_sale(int num, int counter){
45         
46         num = (num + 1) * 2;
47         System.out.println("第"+counter+"个村子卖出的鸭子的数量是：>>>>>>"+(num/2-1));
48         //计数器减1
49         counter--;
50         
51         if(counter > 0){
52             //说明前面鸭子没卖完  递归调用方法 算出该村子卖出的鸭子的数量
53             duck_sale(num,counter);
54         }else{
55             //说明鸭子卖完了
56             System.out.println("鸭子的总数是：>>>>>>"+num);
57         }
58         return num;
59     }
60     /***
61      * 角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。
62      * 求经过多少次可得到自然数1。
63      * 如：输入22，
64      * 输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
65      * STEP=16
66      * 
67      * 算法步骤：
68      * 1)定义计数器counter=0 输入自然数的值
69      * 2)判断n 是否为偶数，若是，则n=n/2 若不是，则n=n*3+1
70      * 3)判断n是否等于1 若是，则输出counter，若不是继续 调用jiaogu()
71      * 
72      * @param n 输入的自然数 所要求的数值
73      * @return 输出最后结果所需要的调用几次
74      */
75     public static int jiaogu(int n, int counter){
76         
77         //这个计数器不可以在这里赋值的，这样每一次调用方法进来之后，都会重置counter的值
78         //int counter = 1;
79 
80         if(n == 1){
81             System.out.println("Step is >>>>>>"+counter);
82         }else{
83             //计数器+1
84             counter++;
85             if(n % 2 == 0){
86                 n = n / 2;
87             }else{
88                 n = n * 3 + 1;
89             }
90             
91             System.out.println("输出当前自然数的值是：>>>>>>"+n);
92             //递归调用
93             jiaogu(n,counter);
94         }
95         return counter;
96     }