递归和回溯
递归
任何调用自身的函数称为递归。递归的要点在于，递归函数调用自身去解决一个规模比原始问题要小一些的问题。
递归函数的格式
- 函数不在递归地情况称作基本情形（base case,也称基本情况）。
- 函数调用自身来执行子任务的情况就称作递归情形（recursive case）。
if (判断是否为基本情形)
return 该基本情形时的函数值
else if (判断是否为另一种基本情形)
return 该基本情形时的函数值
//递归情形
else return (执行某些工作并递归调用)例：n!等于n~1之间所有整数的乘积，起递归定义如下
n! = 1 n=0|1 （基本情形）
n! = n*(n-1)! n>0 （递归情形）
代码如下
public static int Fact(int n) {
// 基本情形：当参数为0或1时，返回1
if(n == 1)
return 1;
else if(n == 0)
return 1;
// 递归情形：返回n*(n-1)!
else
return n * Fact(n - 1);
}递归和内存可视化
public static int Print(int n) {
if (n == 0)
return 0;
else {
System.out.println(n);
return Print(n - 1);
}
}
回溯
回溯是一种采用分治策略进行穷举搜索的方法。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
