作者yauhh (喲)
看板Programming
標題Re: [問題] 適合遞迴的資料結構
時間Tue Mar 22 01:44:49 2011
※ 引述《fjf1980 (聽說 侯佩岑是豬頭)》之銘言：
: ※ [本文轉錄自 C_and_CPP 看板 #1DXuRGWq ]
: 作者: fjf1980 (聽說 侯佩岑是豬頭) 看板: C_and_CPP
: 標題: [問題] 適合遞迴的資料結構
: 時間: Tue Mar 22 01:11:40 2011
: 忘記哪一年的一國考題目：
: 適合用來解決遞迴 (recursion) 問題的資料結構為何？其如何運作？
: 我覺得是陣列
: 因為有很多會用到遞迴演算法的結構都用陣列，像是二元樹的運算
: 還有陣列也剛好可以一格一格跳下去做運算
: 請問各位高手對這個問題有沒有些想法，建議，希望指教一下，感謝！
: ps.找到問題了: 適合用來解決遞迴 (recursion) 問題的資料結構為何？其如何運作？
想了一想覺得這個問題好爛. 如果說答案是 stack, 並且只是因為寫 C 語言遞迴
會用到系統堆疊的話,那真是超級沒哏的問答法.
何謂遞迴問題? 就是一個大問題可以拆成一些小問題,小問題的格式與大問題一模一樣.
( 於是可以解決小問題,把小問題的答案放在一起就解決大問題. )
明確地說,適合解遞迴問題的資料結構,當然是任何具備遞迴性質的資料結構啊!
用資料結構直接對應遞迴問題的問題結構,非常容易解決問題.
遞迴的資料結構,就是大結構可以拆成小結構,而且大結構與小結構格式一模一樣.
所以只要能把結構遞迴定義就可以了: 基本要注意到 base case 與 recursive case.
於是 stack 是遞迴結構,因為 stack 多加一個資料也是 stack.
( base case: 空集合 )
於是 linked list 也是遞迴結構了, 鏈接串列多加一筆資料,仍是鏈接串列.
( base case: 空節點或首節點 )
Tree 一定是遞迴結構,任何一棵樹的子項也是樹.
( base case: 空節點 )
陣列,當然也是遞迴結構,因為陣列多加一格,還是陣列.
( base case: 長度為 0 的陣列 )
--
/yau
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.209.55
1F：推 VictorTom:y大的解釋感覺更像Divide & Conquer@@"111.240.167.159 03/22 02:05
2F：→ VictorTom:Wiki上的簡意是: "functions calling111.240.167.159 03/22 02:08
3F：→ VictorTom:themselves". 只是D&C的實作中Recur常被111.240.167.159 03/22 02:09
4F：→ VictorTom:使用就是了:)111.240.167.159 03/22 02:10
5F：推 fjf1980:y大真是強者， 感謝你的解釋 219.84.57.222 03/22 10:00
6F：→ yauhh:不敢當,還沒算多強218.160.208.226 03/22 20:18
7F：→ yauhh:V,你顯然抓錯方向了. 遞迴本來就是D&C,但遞218.160.208.226 03/22 20:19
8F：→ yauhh:迴重要的是大問題與小問題的結構相同. 所以218.160.208.226 03/22 20:19
9F：→ yauhh:可說凡遞迴必定是D&C,但是並不是任何D&C都是218.160.208.226 03/22 20:20
10F：→ yauhh:遞迴.218.160.208.226 03/22 20:20
11F：推 VictorTom:小弟我的意思是, 您對Recur的解釋其實是 220.134.18.177 03/22 21:43
12F：→ VictorTom:Wiki上D&C的解釋; Recur是一種實現它的 220.134.18.177 03/22 21:44
13F：→ VictorTom:方式. 其實小弟的疑問就是您最後說的, 220.134.18.177 03/22 21:45
14F：→ VictorTom:"遞迴必是D&C", 恕小弟再想想先:) 220.134.18.177 03/22 21:46
15F：→ yauhh:我也覺得這樣回答有點鬆散. 原問題是問:218.160.208.226 03/22 21:50
16F：→ yauhh:最適合解決遞迴問題的結構. 並不只是遞迴程218.160.208.226 03/22 21:50
17F：→ yauhh:式用到,而是一種能夠幫助遞迴問題解決的結構218.160.208.226 03/22 21:51
18F：→ yauhh:這樣想如果不是stack就是queue或tree.218.160.208.226 03/22 21:51
19F：推 arcred:這樣看任何一個有序集成的結構都可以是答案 68.98.169.112 03/23 11:26
20F：→ arcred:不過我滿好奇答案的.. 希望不是stack XD 68.98.169.112 03/23 11:28
21F：推 purpose:>都可以是答案 用 queue 也適當? 124.8.130.53 03/23 11:45
22F：推 arcred:嗯...的確FIFO好像不適合 @@ 68.98.169.112 03/23 12:21