递归与循环的效率问题
一摆案例：
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。（0<n<10000）
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
要求：1s内，256M内
考点：1简单循环的效率比递归高；2.利用10007的余数巧妙避开了大数BigInter操的作（这个类的操作效率很慢）。
那么这个时候平时算法学得好的童鞋都会立马写个递归函数，杠杠地，一个递归函数就搞定，多厉害。
publicstatic long fib(int n){
if(n==1 ||n==2)
return 1;
else{
return (fib(n-2)+fib(n-1))%10007;
}
}
然而，你在运行得时候却超过了1s，当n=45的时候，你运行得时间已经超过10s了，更别说n=10000。
那么这个时间就需要用简单循环来解决这个时间问题了：
for(inti=1;i<=n;i++){
if(i ==1 ||i==2) f[i] =1;
else f[i] =(f[i-2]+f[i-1])%10007;
}
这个时候1s内搞定，轻轻松松！！
二．原因分析：
大家都知道递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N*局部变量、N*形参、N*调用函数地址、N*返回值。这势必是影响效率的。
所以，对于简单的问题，能用循环就别用递归。