[問題] 基本的費氏數列-遞迴的問題，麻煩請幫忙

[lovelymomo (lovelymomo)]

版上的高手，大家好…最近才開始學習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
→ TW1943:觀念錯了... http://tinyurl.com/62en5k
→ TW1943:看中間 Computing the recurrence relation for n = 4:
→ nukchichi:我的想法是先處理n=0,n=1,n=2,n =3的case 應該就OK了
→ james732:同樓上，不要一開始就想n=10，想想n=1,2,3,4是怎麼算的
推 lf21201:送10是return (recursiveTest(9)+recursiveTest(8)) 而不
→ lf21201:是(9)+(8)=(17) 每一個遞迴都會呼叫自己直到n==1 || n==2
推 lachtchlee:樓上正中 要害 我鼓掌
→ mars90226:我也覺得一開始就是n=10很難驗算...從小數字開始
推 fanntone:你觀念完全錯了啊!!!!第1項n=0 第2項n=1 你要算第10項
推 fanntone:可是55是第11項合 整個觀念都錯了!
→ lovelymomo:後來看了大大們的推文，再回去仔細推算一遍，已經會了
→ lovelymomo:感謝各位