三亩地 三亩地SAN MU DI · CODE DIARY
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天,欢迎挑你感兴趣的翻一翻。

递归函数的设计方法

递归函数的设计方法

数学归纳法

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; //边界条件的设计 } } }
← 返回列表