递归基础练习题
代码实现及测试用例
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 == 0 102 */ 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 == 0 115 */ 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 <arr[index]){ 126 arr[index+1] = arr[index]; 127 index--; 128 } 129 arr[index+1] = x; 130 return arr; 131 } 132 }