[問題] 遞迴問題

[ptt0720 (濕濕)]

macOS 10.12

GCC

無

我想請問遞迴的意思是直接呼叫自己就算嗎 因為做了好幾題還是很不懂
有沒有哪邊有比較多遞迴的CODE可以參考
河內塔 排列組合 我就搞到頭暈了 主要是流程不太清楚
希望板上能推薦一些教材
還有 有哪些題目是用遞迴比較方便的嗎 因為我發現遞迴的題目都是一些很漂亮的
不知道以後實戰用到的機會多不多？





是這樣的

我想要做一個程式
先給定一個值例如
120
然後給數量
8 (8筆資料)
接著輸入個數 25 30 15 20 30 40 35 10

然後要印出有幾種組合可以使總和=120

我知道把那些資料用陣列來存

但是我要如何用遞迴來找結果

要讓總和等於120
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.105.31.4
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1478877541.A.CAA.html
11/11 23:33
11/11 23:34
11/11 23:35
11/11 23:45
11/11 23:46
~
※ 編輯: ptt0720 (59.105.31.4), 11/12/2016 00:03:51
→ aiwhat: 對於數列第一個數字25有兩種情況：取or不取
→ aiwhat: 取：問題變為在30 15 20 30 40 35 10找出總和為95的組合
→ aiwhat: 不取：在剩下七個數字中找出總和為120的組合
→ aiwhat: 剩下的問題就是什麼時候該停止遞迴
推 youtuuube000: 這問題你可以查看看dynamic programming的背包問題
推 steve1012: 這個可以用一個integer 來模擬所有情形 寫成for loop
→ steve1012:  效率很高
→ steve1012: 想寫遞迴的話Google subset sum recursion
→ steve1012: 有很多教學
→ MOONRAKER: 因為消耗的資源較多 實用上不鼓勵遞迴
→ MOONRAKER: 但有一些剛好就是用遞迴考慮最簡單的問題 或者規模可以
→ MOONRAKER: 控制到相對小的問題 用遞迴解決並無不可
→ MOONRAKER: 把它轉換成iteration可能要浪費更多時間 或不易維護
→ bigpigbigpig: 用 power set 比較快：https://ideone.com/xp9RBc
推 descent: C程序设计的抽象思维, recursive我覺得是可以投資的技巧
→ ptt0720: 我要讓資料都給使用者輸入 如何讓知道哪些輸字是必須要的
→ MOONRAKER: ？輸入過濾用迴圈或regex來match就好 跟遞迴有何關聯