递归函数的设计方法

数学归纳法

step1:验证p(1)成立

step2:验证p(k)成立，那么p(k+1)也成立

step3:联合step1和step2,证明由p(1) -> p(n)成立

例子：

证明：1+3+5+......+2n-1 = n^2

第一步：p(1)=1,成立

第二步：假设：p(n-1) = (n-1)^2 成立

->则 p(n) = p(n-1) +2n-1 = n^2成立

第三步：1，2步成立 ->成立

递归函数设计的三个重要部分

1.给递归函数一个明确的语义

2.实现边界条件的程序逻辑

3.假设递归函数调用返回结果是正确的，实现本层函数逻辑

例子（阶乘）：

import java.util.Scanner; public class factorial { public static void main(String[] args) { System.out.println("请输入要阶乘的正整数数"); Scanner scanner = new Scanner(System.in); int number = scanner.nextInt(); int result = factorial(number); System.out.println(result); } public static int factorial(int number) { if (number > 1) { return number * factorial(number - 1); //保证n-1的正确性 } else if (number == 1) { return 1; //边界条件的设计 } else { return 0; //边界条件的设计 } } }