©2020-2024 ioDraw All rights reserved,
Privacy Policy
直接上代码(附有注解)
package changer.day02; /** * 1.切蛋糕思维 * 2.看看有没有递推公式,或等价转换 */ public class
_02_1什么是递归 { public static void main(String[] args) { //
System.out.println(f1(10)); // f2(1,10); // System.out.println(f3(new
int[]{1,1,1,1,1},0)); // System.out.println(reverse("abcd","abcd".length()-1));
System.out.println(fib(5)); } /** * 求n的阶乘 * 找重复:
n*(n-1)的阶乘,求n-1的阶乘是原问题的重复,(规模更小) -子问题 * 找变化: 变化的量作为参数 * 找边界: 出口 * @return */
static int f1(int n){ if(n == 1) return 1; return n * f1(n-1); } /** * 打印i到j *
找重复: * 找变化: 变化的量作为参数 * 找边界: 出口 * @param i * @param j */ static void f2(int i,
int j){ if (i>j) return; System.out.println(i); f2(i + 1,j); } /** *
对arr的所有元素求和 * 找重复: * 找变化: 变化的量作为参数 * 找边界: 出口 */ static int f3(int[] arr,int
begin){ if(begin == arr.length-1) return arr[begin]; return arr[begin] +
f3(arr,begin+1); } /** * 反转字符串 * 找重复: * 找变化: 变化的量作为参数 * 找边界: 出口 */ static
String reverse(String src,int end){ if (end == 0) return "" + src.charAt(0);
return src.charAt(end) + reverse(src, end - 1); } /** * 求斐波那切数列 * 找重复: * 找变化:
变化的量作为参数 * 找边界: 出口 */ static int fib(int n){ if(n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2); } /** * 最大公约数 * 找重复: * 找变化: 变化的量作为参数 * 找边界: 出口
*/ static int gcd(int m,int n){ if(n==0){ return m; } return gcd(n,m%n); } }