递归基础练习题

代码实现及测试用例

1 package recursion;  2   3 import java.util.Arrays;  4   5 /**  6  * @author zsh  7  * @company wlgzs  8  * @create 2019-02-15 16:08  9  * @Describe 递归练习 10  */ 11 public class Main1 { 12     public static void main(String[] args) { 13         System.out.println("------------1、求n的阶乘----------------"); 14         System.out.println(f1(3)); 15         System.out.println("------------2、打印i到j-----------------"); 16         f2(1,3); 17         System.out.println("---------3、对arr所有元素求和-----------"); 18         System.out.println(f3(new int[]{1,2,3,4,5},0)); 19         System.out.println("------------4、翻转字符串---------------"); 20         String str = "hello"; 21         System.out.println(reverse(str,str.length()-1)); 22         System.out.println("-----------5、斐波拉契数列--------------"); 23         System.out.println(fib(5)); 24         System.out.println("-----------6、最大公约数----------------"); 25         System.out.println(gcd(10,6)); 26         System.out.println("--------7、递归实现插入排序-----+-------"); 27         int[] arr = new int[]{5,4,9,6,3}; 28         System.out.println(Arrays.toString(insertSort(arr,arr.length-2))); 29     } 30  31     /** 32      * f1(n)求n的阶乘 -->f(n-1)求n-1的阶乘 33      * 找重复：n*(n-1)！，求(n-1)！是原问题的重复(规模更小) --子问题 34      * 找变化：变化的量应该作为参数 35      * 找边界：出口 36      */ 37     static int f1(int n){ 38         if (n == 1) 39             return 1; 40         return n*f1(n-1); 41     } 42  43     /** 44      * f2(i,j)打印i到j 45      * 找重复：打印i，f2（i+1，j） --子问题 46      * 找变化：变化的量应该作为参数 47      * 找边界：出口 终止的条件 48      */ 49     static void f2(int i,int j){ 50         if (i>j){ 51             return; 52         } 53         System.out.println(i); 54         f2(i+1,j); 55     } 56  57     /** 58      * f3(arr,begin) 对arr所有元素求和 59      * 找重复：arr[begin] + f3(arr,begin+1) --子问题 60      * 找变化：变化的量应该作为参数 begin作为变化的量,相当于头指针。 61      * 找边界：出口 终止的条件 头指针与数组最后一个元素的索引相同 62      */ 63     static int f3(int[] arr,int begin){ 64         if (begin == arr.length-1){ 65             return arr[begin]; 66         } 67         return arr[begin] + f3(arr,begin+1); 68     } 69  70     /** 71      * reverse(str,end) 翻转字符串 72      * 找重复：str.charAt(end) + reverse(str,end-1) --子问题 73      * 找变化：变化的量应该作为参数 end作为变化的量,相当于尾指针。 74      * 找边界：出口 终止的条件 end == 0 75      */ 76     static String reverse(String str,int end){ 77         if (end == 0){ 78             return ""+str.charAt(0); 79         } 80         return str.charAt(end) + reverse(str,end-1); 81     } 82  83     /** 84      * fib(n) 斐波拉契数列 1 1 2 3 5 8 ..... 85      * 找重复：fib(n) = fib(n-1) + fib(n -2) --子问题 86      * 找变化：变化的量应该作为参数 n。 87      * 找边界：出口 终止的条件 n == 1 || n == 2 88      */ 89     static int fib(int n){ 90         if (n == 1 || n == 2){ 91             return 1; 92         }else { 93             return fib(n-1)+fib(n-2); 94         } 95     } 96  97     /** 98      * gcd(m,n) 最大公约数 辗转相除法 99      * 找重复：gcd(m,n) = gcd(n,m%n) --子问题100      * 找变化：变化的量应该作为参数 n。101      * 找边界：出口 终止的条件 n == 0102      */103     static int gcd(int m,int n){104         if (n == 0){105             return m;106         }107         return gcd(n,m%n);108     }109 110     /**111      * insertSort(arr,k) 递归实现插入排序112      * 找重复：insertSort(arr,k-1) 将k-1个排序后，把arr[k]插入到前面的数据中 --子问题113      * 找变化：变化的量应该作为参数 k。114      * 找边界：出口 终止的条件 k == 0115      */116     static int[] insertSort(int[] arr,int k){117         if (k == 0){118             return arr;119         }120         //对前k-1个元素排序121         insertSort(arr,k-1);122         //把k位置上的元素插入到前面的部分123         int x = arr[k];124         int index = k -1;125         while (index >= 0 && x 

 递归基础总结见博客：