版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1342040
\*\* java递归问题小结\*\*
对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递推的出口,这样原问题就有递推得解。
在做递归算法的时候,一定要把握住出口,也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的,就是一个条件,当满足了这个条件的时候我们就不再递归了。
关键要抓住的是:
(1)递归出口
(2)逐步向出口逼近
下面举一些常用的例子
1 如 1+2+3+4+5+.......100
/**
* 下面的算法是算1+2+3+……的
* @param num
* @return
*/
public static long sum(int num) {
if (num > 0) {
return num + sum(num - 1); // 调用递归方法
} else {
return 0; // 当num=0时,循环结束
}
}
2
/**
* 下面的算法是算1+1/2+1/3+……;
* @param n
* @return
*/
public static double add(int n){
if(n==1){
return 1.0/1;
}
else{
return 1.0/n + add(n-1);
}
}
3
/**
* 下面的算法是算1_*2*_3*.......
* @param input
* @return
*/
public static double multiplication(long input){
if(input==1){
return 1;
}else{
return input*multiplication(input-1);
}
}
4 Fibonacci数列:1,1,2,3,5,8,13……
要求:找出数列中指定index位置的数值
private static long fab(int index) {
if (index == 1 || index == 2) {
return 1;
} else {
return fab(index - 1) + fab(index - 2);
}
}