作者lovelymomo (lovelymomo)
看板java
标题[问题] 基本的费氏数列-递回的问题，麻烦请帮忙
时间Mon Aug 8 01:25:40 2011
版上的高手，大家好…最近才开始学习Java，目前碰到了一个问题
始终想不出来内部是如何去执行，所以厚着脸皮上来，请教版上高手
如果有不符合版规，麻烦请告知，会马上删除，谢谢
============================================================
题目是这样子的
Q。使用递回来解决费氏数列
费氏数列=>0.1.1.2.3.5.8.13.21.34.55.......(後1个数为前2个数的总合)
public class Fibonacci
{
public static void main(String[] args)
{
recursiveTest(10);
}
public static int recursiveTest(int n)
{
if(n==1)
return 1;
else if(n==2)
return 1;
else
return recursiveTest(n-1)+recursiveTest(n-2);
}
}
以上执行後，结果应该为55
但自己推算，结果总是不正确
所以想把自己的想法打出来，请大家帮忙改正我不对的地方
在方法recursiveTest中，若要停止递回，应该是在 n==1 或 n==2 的时候，是吗？
那假定使用recursiveTest时，传进一个n值=10
就并不会去执行到 if(n==1)及else if(n==2) 这二行程式码
所以就直接跳到 return recursiveTest(n-1)+recursiveTest(n-2);这里
代入n=10的话，就是 (10-1)+(10-2) 就是9+8=17
那又return 17 这个值回去的话，不就变成无穷回圈了吗？
所以以上我这样推测并不对。
那再假定下面这样
n=10;
(10-1)+(10-2) = 17 return (10-2) 的值 8 回去
n=8;
(8-1)+(8-2) = 13 return (8-2) 的值 6 回去
n=6;
(6-1)+(6-2) = 9 return (6-2) 的值 4 回去
n=4;
(4-1)+(4-2) = 5 return (4-2) 的值 2 回去
这时n==2 所以又return 1;
那再把以上相加？ 17+13+9+5+1=45。 答案也不是55 >"<
想请问，我是逻辑哪边有问题。
因为想详述自己的想法，所以打了比较多，谢谢您耐心的看完
虽然是新手，但感觉这是一段很简单的代码，却困扰了我很久
觉得学起来有点灰心阿 @__@
所以麻烦大家帮帮我，谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.115.1.232
2F：→ TW1943:看中间 Computing the recurrence relation for n = 4: 08/08 01:54
3F：→ nukchichi:我的想法是先处理n=0,n=1,n=2,n =3的case 应该就OK了 08/08 03:02
4F：→ james732:同楼上，不要一开始就想n=10，想想n=1,2,3,4是怎麽算的 08/08 04:05
5F：推 lf21201:送10是return (recursiveTest(9)+recursiveTest(8)) 而不 08/08 07:31
6F：→ lf21201:是(9)+(8)=(17) 每一个递回都会呼叫自己直到n==1 || n==2 08/08 07:33
7F：推 lachtchlee:楼上正中 要害 我鼓掌 08/08 08:31
8F：→ mars90226:我也觉得一开始就是n=10很难验算...从小数字开始 08/08 10:38
9F：推 fanntone:你观念完全错了啊!!!!第1项n=0 第2项n=1 你要算第10项 08/08 16:49
10F：推 fanntone:可是55是第11项合 整个观念都错了! 08/08 16:51
11F：→ lovelymomo:後来看了大大们的推文，再回去仔细推算一遍，已经会了 08/09 12:24
12F：→ lovelymomo:感谢各位 08/09 12:25