C語言遞迴問題

匿名 2012-03-09 10:43:40 ‧ 5881 瀏覽

分享至

以下的程式，我看不太懂，這是一個遞迴的程式實例

可否請問這程式的執行方式呢??

int factorial (int j){ <==這地方看起來怪怪的，int j…??
if(n==1)
return(1);
else
return(n*factorial(n-1));
}
void main(void){
int i;
for(i=0;i<5;i++)
printf("%d = %d\n",i,factorial(i));
}

總裁 iT邦好手 1 級 ‧ 2012-03-09 11:07:11 檢舉

您有去trace過這隻程式嗎??應該有BUG吧...

海綿寶寶 iT邦大神 1 級 ‧ 2012-03-09 13:58:24 檢舉

那個0傳進去就爆了

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

4 個回答

賽門

iT邦超人 1 級 ‧ 2012-03-09 15:03:19

最佳解答

int factorial (int j) 修正為
int factorial (int n)

for(i=0;i<5;i++)
printf("%d = %d\n",i,factorial(i));
版大的意思應該是:
i=0.....結果為0
i=1.....結果為1
i=2.....結果為2*1=2
i=3.....結果為3*2*1=6
i=4.....結果為4*3*2*1=24
i=5.....結果為5*4*3*2*1=120

但由程式中...
if(n==1)
return(1);
else
return(n*factorial(n-1));

沒有特別處理n=0的情況, 所以, 就會
i=0....結果0*(-1)*(-2)*(-3)*(-4)*.......成了無盡迴圈...直到Overflow!

所以, 請再加個處理n=0的判斷.

回應 3
分享
檢舉

總裁 iT邦好手 1 級 ‧ 2012-03-09 15:19:11 檢舉

0不用判斷，別傳進去就好了...

海綿寶寶 iT邦大神 1 級 ‧ 2012-03-09 20:15:05 檢舉

cdfu提到：
0不用判斷，別傳進去就好了

本草綱目寫的很清楚，0!=1
不傳進去
你是想讓他被蛋掉呀

匿名檢舉

難怪我拿上面的程式下去測，就當了!!原來變迴圈了~~呵呵~

登入發表回應

fillano

iT邦超人 1 級 ‧ 2012-03-09 11:49:42

視覺debug的話，看起來j應該改成n吧？

回應
分享
檢舉

登入發表回應

wiseguy

iT邦超人 1 級 ‧ 2012-03-09 23:42:33

所以歸納起來就是兩處要改：

(int j) 修正為 (int n)
if(n==1) 修正為 if(n<2)

回應
分享
檢舉

登入發表回應

tom1686

iT邦新手 2 級 ‧ 2012-03-10 09:38:57

前面幾位大師及高手都已把問題點出來了，我這個初學者來稍彙整一下

factorial的定義：
一個正整數的階乘（英語：factorial）是所有小於或等於該數的正整數的積，並且有0的階乘為1。http://zh.wikipedia.org/wiki/%E9%98%B6%E4%B9%98

wiseguy 的歸納已處理掉版主參考來的程式碼中的Bug

另外

&lt;pre class="c" name="code">printf("%d = %d\n",i,factorial(i));
&lt;==看到這一段的factorial(i)

是不是就要跳下面這一段
int factorial (int j){ 
if(n==1)
return(1);
else
return(n*factorial(n-1));
}

...沒錯，就是這樣，只要有看到呼叫函式就是跳進去，進去後又看到函式再繼續跳進去

遞迴函式必須特別注意返回的臨界判斷，否則會成為 simon581923 所說的無限遞迴進而造成 Overflow!...那這是為什麼呢？因為每次呼叫factorial(int n)時都會把(int n) PUSH進stack，等執行完 return 後才會釋放該stack。

題外話：
即使判斷式沒有錯誤，但若輸入的n過大還是有機會撐爆stack，所以使用遞迴需要非常小心，儘可能還是使用for迴圈為佳。

http://squall.cs.ntou.edu.tw/cprog/Materials/FactorialProgram.html

http://wywu.pixnet.net/blog/post/22014250-%5B%E6%95%B8%E5%88%97%5D-%E9%9A%8E%E4%B9%98-(factorial)---100!-%E7%82%BA%E5%A4%9A%E5%B0%91%3F