函数递归的问题 - 黑马程序员技术交流社区

public class Test {
/*
* 采用递归方法计算1++2+3+....+100; 如果num大于0则将num-1后继续执行此方法直至num=0,递归结束
*/
public static int sum(int num) {
if (num > 0) {
return sum(num - 1) + num;
} else {
return num;
}
}
public static void main(String args[]) {
// 输出1++2+3+....+100的和
System.out.println(sum(100));
}
}

复制代码

给你我总结的一点东西.
递归的内存消耗
当于递归算法,递归的使用只能限于精简算法,否则递归的效率会奇低.
----------------------------------------------------------------
示例: 论坛找的例子.
public class PruduceCattle {
/** 一个农夫养了一头牛，三年后，这头牛每一年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……
* 问农夫10年后有多少头牛?n年呢?(不考虑其他因素，只考虑此数学问题)
* 规律:即f(n)=f(n-2)+f(n-3)+f(n-4)(n > 4);这个用递归效率奇低.
* 我找的规律:f(n)=f(n-1)+f(n-3);(n>3)
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Long begin=System.currentTimeMillis();
System.out.println(getCattleCount(1000));
System.out.println(System.currentTimeMillis()-begin+"毫秒");
//我的算法时间:
/*50 1000
83316385 4.239507006748923E165
0毫秒 31毫秒*/
/*Long begin=System.currentTimeMillis();
System.out.println(getSum(50));
System.out.println(System.currentTimeMillis()-begin+"毫秒");*/
//递归算法的时间:
/*50 1000
565毫秒超过5分钟,我等了很久没出结果
*/
}
public static int getSum(int years) {//他人的示例
if (years == 0)
return 0;
else if (years >= 1 && years <= 3)
return 1;
else if (years > 3)
return getSum(years - 2) + getSum(years - 3) + getSum(years - 4);//这里相当于一个三层嵌套for循环
else
System.out.println("输入有误，请重新输入！");
return years;
}
public static double getCattleCount(int n){
double sum=0;
double first=1;
double second=1;
double thread=1;
for(int i=0;i<n-3;i++){//这是一个线性算法,程序算法,只循环n-3次.
sum=first+thread;
first=second;
second=thread;
thread=sum;
}
if(n<=3)
return 1;
else return sum;
}
}

复制代码

关于递归的使用
1:使用递归,必须是带着能减少循环次数的目的去递归的.否则就会适得其反.看似代码简单.却会造成程序内存崩溃.
2:如果递归的次数过多,就避免使用递归求解,或者优化递归次数.
关于递归的高效使用:
//求一个数的任一次方
public static long pow(int x,int n){
if(n==0)
return 1;
if(n%2==0)
return pow(x*x,n/2);//n是递归次数.n/2次递归就代表程序运行次数会少于n/2
else return pow(x*x,n/2)*x;
}
/*如:pow(2,64)求2的64次方:运算次数为:64->32->16->8->4->2->1->0 共8次求解
而pow(2,1200)运算次数为:1200-600-300-150-75-37-18-9-4-2-1-0 共12次求解

复制代码