請問遞迴的原理

Question

請問能有人用較簡單的方式來解釋遞迴嗎
遞迴真的超出了我的想像空間了

Answer 1

恩恩，前面兩位大概解釋了程式語言中遞迴的運作原理，我想補充的是，遞迴在解決問題中扮演的角色。

今天你寫一個副程式來解決某一問題、達成某功能。函示input value輸入問題，然後 output value輸出結果，而函示本身有一些運算過程來進行解決問題的步驟。這是函示基本運作的方式。

函示之所以會寫成遞迴的方式，通常是因為問題太難解了，沒有辦法一次解完...所以，函示本身可能會以下述方法運作：
if( 問題 is easy )
進行運算解決問題
else
分割問題為數個更小的問題，丟給別人處理

所以遞迴函示會依照兩個方式來運作，如果問題簡單，就直接把問題幹掉，然後輸出結果。如果問題太難，就想辦法簡化分割成為幾個小問題，然後找別人幫忙解決小問題，等小問題解決後，把答案組合起來，輸出。

這時候衍身另一個想法....把第一次簡化後的問題，再丟給原函示處理。
就好像 一個問題丟給func_a()，可是func_a()沒有辦法一次解決，就予以分解，然後再次呼叫func_a()來處理這個簡化後的問題......反覆下去，只要問題逐次簡化，總有一個func_a()能夠解決問題！！之後答案不斷back trace，問題就完全解決了！！！

阿阿阿阿阿，輸入框格能打多少字阿？

example：寫一個程式去運算階層
int func_foo(int input){
int temp;
if( input ==1 ){/* 哈 要我運算1! 這太簡單了！！*/
return 1;/*答案就是1阿*/
}
else{/*嗚嗚，問題太難，我先分解再找別人*/
temp = func_foo(input-1); /*這東西的一部份是 比他小一的階層*/
return input * temp /* 然後乘上自己就是解答了*/
}
}

程式運作:
func_foo(3)
嗚嗚嗚太難，我只知道答案是3*func_foo(2),
嗚嗚嗚太難，我只知道答案是2*func_foo(1),
哈哈真簡單，答案是1
喔，答案是 2*1 = 2
喔，答案是 3*2 = 6
喔，答案是 6

如此.....


打這麼多，分數比較高嗎...Orz.....

Answer 2

就像你往上爬到樓層N(遞迴的迴圈N)
在每一樓放一個東西(單次計算的結果...遞迴的重點I)
等到了最頂樓(迴圈最終的次數)
然後下樓~一層一層的把計算結果帶回來(遞迴的重點II)
最後回到一樓(迴圈結束的地方)
並把值return回去
迴圈一定要定義迴圈結束的條件
不然就陷入無限迴圈
遞迴就是要自己跟自己做計算(例如算N的N次方)
其實不用遞迴也能作同效果的計算
用FOR LOOP也是很好用啦,又可以明確定義何時BREAK
降低程式出錯

Answer 3

你知道怎麼呼叫函式吧~~
其實遞迴只呼叫函式的應用而己。
就 像A( ) 運算到一半需要去CALL B( ) ﹐B( )算到一半要去CALL C( ) 一樣
只是差在 遞迴中 A﹐B ﹐C都是同一個﹐可以CALL很多次
(因為CALL太多次會造成堆疊暴掉﹐所以不是無限多次)
這樣了解了嗎﹖