一個關於遞迴的問題

D9105032

我剛學程式設計
小弟我有一個遞迴的問題想要問各位大哥:
請問下列程式fact(4)的回傳值為??

{ if (n==0) return 1;
   else
      return 3*fact(n-1);
}

答案是:81
但是我不知道怎麼算出來的
哪一位可以幫我解答一下嗎??
感激不盡~~

snowflying

這遞迴就是求 3 的非負整數次方呀

fact(4)
= 3 * fact(4-1)
= 3 * [3 * fact(3-1)]
= 3 * 3 * [3 * fact(2-1)]
= 3 * 3 * 3 * [3 * fact(1-1)]
= 3 * 3 * 3 * 3 * 1
= 3^4
= 81

ggyou300atm

它把括號裡面的數當成n,所以目前n=4
4≠0，所以if不做，做else
Else做的是把3*fact(4-1)的值回傳
Fact(4)=3*fact(3)  但不知道fact(3)是多少
Fact(3)的3≠0，所以if不做，做else
以此類推…
最後會做到fact(0),
Fact(0)有符合if的條件，所以做if不做else
Fact(0)=1
這時候有解，就可以遞迴了

Fact(4)=3*fact(3)     
Fact(3)=3*fact(2)     ↑
...

瀏覽完整內容，請先 註冊 或 登入會員

Fact(n) = 3*Fact(n-1) = 3^2*Fact(n-2) = ... = 3^n*Fact(0) = 3^n

hichcock

妳的 IDE 不能設中斷點嗎
可以設的話就一步一步執行就知道答案了

遞迴要自已多代幾次才會有感覺，重點是每次呼叫遞迴時引數的變化(fact(n-1))，還有最後的終止條件(n==0)。

tevin

在程式上加個Break point吧
看程式執行過程比較有感覺
也比較能了解之間的來龍去脈