[程式]stack與recursion

[cpyi]

這是之前郭先生跟我分享的題目，好像是資工系的習題，題目洋洋灑灑好幾頁，看了就懶得做。後來我看一看，又參考他給我的一份範例的程式碼，把他整理了一下，發覺這真的是一個不錯的習題。題目的檔案我懶得找了，基本是堆疊相關的主題，堆疊(stack)是一種典型的資料結構，我想大家google一下就能知道它的運作，所以我也不想在這裡多談。

我想談的是stack與recursion，recursion就是遞迴。現在設想一種情境，把遞迴的路徑記錄下來，其實堆疊就是一種最自然的資料結構，遞迴一層，就push一個新的資料，把這層的資料記錄下來，回到上一層caller時，就pop掉這層記錄的資料。

這個題目一部分是實作遞迴的類別，另一部分是要印出1到N自然數集合的所有子集合。第二部分用遞迴實作，對一個元素而言，不是有，就是沒有，從第一個元素地回到最後一個元素，自然就能找到所有子集合，可是問題是，怎麼紀錄子集合的元素，第一部分做的stack就是最佳工具，利用push和pop的特性，能完美紀錄。本來題目說印出的時候要一個一個pop出來，可是我把它改了一下，直接用stack的member function實作，比較好用。

範例程式碼：

http://www.nba.nctu.edu.tw/~cpyi/stack.cpp