PTT推薦

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

看板Gossiping標題Re: [問卦] 寫程式會用遞迴 大概是什麼程度?作者
utomaya
(烏托馬雅)
時間推噓12 推:14 噓:2 →:14

※ 引述《jason851124 (YeeeEX)》之銘言:
: 乳提
: 在寫code的時候
: 常用迴圈來設條件 讓程式來達成想要的目的
: 如for, while, do while
: 但有另一種比較進階的概念叫遞迴
: 就如同全面啟動一樣 一層一層的進入夢靨
: 一層一層的呼叫自身函數 最後在慢慢逃脫
: 這種架構在撰寫的時候 邏輯要更清晰
: 想問可以習慣寫遞迴的人
: 大概是什麼等級阿? 有掛?

以前在C語言板看過一個簽名檔
一個在程式語言界有名的人說了一句話:「遞迴只在天上有,凡人應該用迴圈」
可能對方是名人,大家都奉為圭臬

我一點都不同意
舉個簡單例子好了
一個陣列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++)
{
//.....
//以下做特殊處理
}
}

}
那如果取20個咧,不就寫到昏倒
以前在冼鏡光的名題精選百則<使用C語言>有提到一個方法,不用遞迴,也不用上述作法列出K個元素的子集
可是非常難懂,是60年代的計算機科學家就發明出來的方法
因為非常難懂(至少對我),一陣子沒讀又忘了

可是這種陣列a[]取任意n個,用遞迴來做非常好寫
我都這樣寫
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很常用到這種遞迴

--

https://projecteuler.net/recent 歐拉編程競賽
https://projecteuler.net/problem=829 最新一題是個簡單題

--

※ PTT留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.71.38.104 (臺灣)
PTT 網址
※ 編輯: utomaya (219.71.38.104 臺灣), 02/14/2023 22:27:56

renna038766 02/14 22:26寫成python好嗎

saygogo 02/14 22:27用鉤吐就好了

PPCYes 02/14 22:27這裡是八

l88 02/14 22:28那是你的loop寫錯吧 取n個n是變數當然不是一

l88 02/14 22:29層層寫啊 當然recursive的code總是比較精簡

l88 02/14 22:29這根本廢話 以DP來說大多數情況top down都比

l88 02/14 22:29bottom up容易寫啊 但遞迴現實中就是要考慮

l88 02/14 22:30stack overflow阿...像Python我印象中>999就

Nigger5566 02/14 22:30你太爛吧,我兩層就能選n個了

l88 02/14 22:30會error了(層數應該可以改 但就是有這限制)

ggirls 02/14 22:30我問chat就好。你下去吧

heyjude1118 02/14 22:30情人節看八卦討論程式

※ 編輯: utomaya (219.71.38.104 臺灣), 02/14/2023 22:32:49

wonder007 02/14 22:33你為了j=i+1 k=i+2多開兩層for幹嘛

utomaya 02/14 22:34k=j+1 是你眼睛沒看清楚

hw1 02/14 22:54都隨意了一開始直接挑出20個index不就好了

utomaya 02/14 23:04這應該叫列出K個元素的所有子集

utomaya 02/14 23:04這是個程式語言中有名的基本訓練

utomaya 02/14 23:05一開始用"隨意" 讓你誤會了 不好意思

pshuang 02/14 23:18亂數取n個 index 就好了啊 你是在寫三小

Nigger5566 02/14 23:19我也誤會了==收回你太爛,抱歉,我爛

DDxMM 02/14 23:32坐等stack爆掉

b0920075 02/14 23:33遞迴也不一定都會 stack overflow,可

b0920075 02/14 23:33以用 tail recursion

jecint1707 02/15 00:51糟糕 完全看不懂

hinanaitenco 02/15 01:09不會用array裡裝index喔 笑死

NewPassat 02/15 01:25太深stack爆給你看

saedn 02/15 04:36嗚嗚 第一行就死腦筋了

bassmaster 02/15 06:14看不懂取任意三個是啥,你這迴圈跑的

bassmaster 02/15 06:14明明就是a.Length個元素的集合取所有

bassmaster 02/15 06:14可能的子集合