Re: [問題] 適合遞迴的資料結構

[yauhh (喲)]

※ 引述《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
推 VictorTom:y大的解釋感覺更像Divide & Conquer@@"
→ VictorTom:Wiki上的簡意是: "functions calling
→ VictorTom:themselves". 只是D&C的實作中Recur常被
→ VictorTom:使用就是了:)
推 fjf1980:y大真是強者， 感謝你的解釋
→ yauhh:不敢當,還沒算多強
→ yauhh:V,你顯然抓錯方向了. 遞迴本來就是D&C,但遞
→ yauhh:迴重要的是大問題與小問題的結構相同. 所以
→ yauhh:可說凡遞迴必定是D&C,但是並不是任何D&C都是
→ yauhh:遞迴.
推 VictorTom:小弟我的意思是, 您對Recur的解釋其實是
→ VictorTom:Wiki上D&C的解釋; Recur是一種實現它的
→ VictorTom:方式. 其實小弟的疑問就是您最後說的,
→ VictorTom:"遞迴必是D&C", 恕小弟再想想先:)
→ yauhh:我也覺得這樣回答有點鬆散. 原問題是問:
→ yauhh:最適合解決遞迴問題的結構. 並不只是遞迴程
→ yauhh:式用到,而是一種能夠幫助遞迴問題解決的結構
→ yauhh:這樣想如果不是stack就是queue或tree.
推 arcred:這樣看任何一個有序集成的結構都可以是答案
→ arcred:不過我滿好奇答案的.. 希望不是stack XD
推 purpose:>都可以是答案   用 queue 也適當?
推 arcred:嗯...的確FIFO好像不適合 @@