PTT推薦

Re: [問卦] 寫程式會用遞迴 大概是什麼程度?

看板Gossiping標題Re: [問卦] 寫程式會用遞迴 大概是什麼程度?作者
dzwei
(Args&&... args)
時間推噓 6 推:6 噓:0 →:1

※ 引述《utomaya (烏托馬雅)》之銘言:
: 一個在程式語言界有名的人說了一句話:「遞迴只在天上有,凡人應該用迴圈」
: 可能對方是名人,大家都奉為圭臬
: 我一點都不同意
: 舉個簡單例子好了
: 一個陣列a[]取任意3個,用迴圈怎麼寫?
: for(int i=0;i<a.size();i++)
: {
: for(j=i+1;j<a.size();j++)
: {
: for(k=j+1;k<a.size();k++)
: {
: //.....
: //以下做特殊處理
: }
: }
: }


這是保守、安全的寫法
請不要小看它
並且多了解
編譯器的最佳化
也不要小看編譯器最佳化
因為他能幫你優化這個"有限迴圈"

原PO說的遞歸
的確是可以簡化程式不少
讓我想到刷提二元樹反轉的時候
這個很好用
參考:
https://tinyurl.com/2p89ndhx

拉回正題 刷提/考試好用
但實際上?

以原PO上一篇說的 當例子

: void recur(int tl, int level, int start)
: {
: if(level==0)
: {
: //以下做特殊處理
: // ......
: return;
: }
: for(int i=start;i<a[].size();i++)
: {
: recur(tl,level-1,i+1);
: }
: }
: 在最後一層幹掉就好
: 我在ProjectEuler很常用到這種遞迴

我們調用它

int main()
{

recur(隨便數字, 狗幹大的數字, 隨便數字);
}


你編譯通過了
一些機器執行
卻跑出
https://zh.wikipedia.org/wiki/Stack_Overflow

沒錯
鼎鼎大名的stackoverflow
名稱就是這樣來的

你在stackoverflow
還是能找到不少關於
遞歸造成stackoverflow的例子

總之
遞歸慎用
特別是要遞歸很多次
並且你的函式偏複雜

--

※ PTT 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.178.242 (臺灣)
PTT 網址

pumapupa 02/14 22:50以前不知道call stack的時候很喜歡遞迴

ronga 02/14 22:57古早人愛用遞迴 某方面是因為容量

sxy67230 02/14 23:02現代蠻多上層語言會防呆避免遞迴深度

hw1 02/14 23:23遞迴的好處就是想法直覺 大拆小一路拆到底 只

hw1 02/14 23:23要考慮n=1的情況就好

horseface 02/15 00:11問題是backtracking問題只能用遞迴啊

kindaichitom 02/15 10:07應該說backtracking用遞迴比較直覺