本節書摘來自華章計算機《計算機系統:核心概念及軟硬體實作(原書第4版)》一書中的第2章,第2.7節,作者:[美] j. 斯坦利·沃法德(j. stanley warford)著, 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
2.4節
1.主程式第一次調用圖2-25中的函數sum,從第二次開始它就自己調用自己。*(a)該函數總共被調用了多少次?(b)畫出函數第三次被調用後,主程式變量和運作時棧的情況。應該有3個棧幀。(c)畫出從(b)調用傳回前,主程式變量和運作時棧的情況。應該有3個棧幀,不過内容和(b)的不同。
2.給出圖2-28中函數bincoeff的調用樹,調用樹的畫法如圖2-30所示,主程式中的調用語句如下:
*(a)bincoeff(4,1) (b)bincoeff(5,1)
(c)bincoeff(3,2) (d)bincoeff(4,4)
(e)bincoeff(4,2)
該函數被調用了多少次?程式執行期間,運作時棧上棧幀的最大數量是多少?程式是按照什麼順序進行調用和傳回的?
3.對練習2中的情況,畫出從下列函數調用傳回前的運作時棧,運作時棧的畫法如圖2-29所示。
*(a)bincoeff(2,1) (b)bincoeff(3,1)
(c)bincoeff(1,0) (d)bincoeff(4,4)
(e)bincoeff(2,1)
在(e)中,bincoeff(2,1)被調用兩次,畫出從第二次對該函數進行調用傳回前的運作時棧。
4.給出圖2-32中逆轉字元串數組字母順序的程式的調用樹,調用樹的畫法如圖2-30所示。函數reverse被調用了多少次?在運作時棧上配置設定的棧幀最大數量是多少?畫出第三次調用函數reverse後的運作時棧。
5.斐波那契數列是
每個斐波那契數列中的數是數列中它前面兩個數之和。數列最開始有兩個數,遞歸地定義為
fib(0)=0
fib(1)=1
fib(n)=fib(n - 1) + fib(n - 2)n > 1
畫出下列斐波那契數的調用樹:
(a)fib(3) (b)fib(4) (c)fib(5)
對上述每個調用,fib被調用了多少次?在運作時棧上被配置設定的棧幀最大數量是多少?
6.對于問題2.15中漢諾塔問題的解決方案,畫出4個盤子情況的調用樹。程式被調用了多少次?運作時棧上棧幀的最大數量是多少?
7.神秘數字遞歸地定義為
myst(0)=2
myst(1)=1
myst(n)=2*myst(n - 1) + myst(n - 2)n > 1
(a)畫出myst(4)的調用序列。(b)myst(4)的值是什麼?
8.檢查下面的c++程式。(a)畫出過程最後一次被調用後的運作時棧。(b)程式的輸出是什麼?