通過(guò)模型對(duì)程式的解析挪凑，可以得到計(jì)算過(guò)程瓶珊，其中一些過(guò)程因?yàn)榻Y(jié)構(gòu)較通用，所以被整理為典型過(guò)程供大家學(xué)習(xí)蟹演。需要注意的是诵原，在計(jì)算過(guò)程的學(xué)習(xí)中要分清程式與過(guò)程的區(qū)別英妓，過(guò)程是通過(guò)模型對(duì)程式的解析產(chǎn)生的計(jì)算步驟挽放，所以一個(gè)遞歸的程式其過(guò)程可能是迭代的绍赛。
線性遞歸
我們使用替換模型分析時(shí)可能會(huì)發(fā)現(xiàn)，有些程式的過(guò)程會(huì)先展開(kāi)再收斂辑畦，通常這種過(guò)程就是遞歸過(guò)程吗蚌，又因?yàn)樵撨^(guò)程的時(shí)間增長(zhǎng)趨勢(shì)為 O(n)。所以稱(chēng)為線性遞歸過(guò)程纯出，其空間增長(zhǎng)趨勢(shì)也為 O(n)蚯妇。比如敷燎，下列計(jì)算階乘的程式為線性遞歸過(guò)程：
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
解析后的計(jì)算過(guò)程如下圖：
線性迭代
線性迭代也是通過(guò)替換模型解析程式時(shí)生成，此類(lèi)過(guò)程即不會(huì)展開(kāi)也不會(huì)收斂箩言，但在每一步都會(huì)保存當(dāng)前步驟的狀態(tài)數(shù)據(jù)硬贯，依靠狀態(tài)數(shù)據(jù)的迭代產(chǎn)生下一步計(jì)算。也因?yàn)樵撨^(guò)程的時(shí)間增長(zhǎng)趨勢(shì) O(n)陨收，所以又稱(chēng)為線性迭代過(guò)程饭豹。
雖然線性迭代過(guò)程的時(shí)間增長(zhǎng)趨勢(shì)與線性遞歸過(guò)程一樣，但線性迭代過(guò)程空間增長(zhǎng)趨勢(shì)為 `O(1)
务漩，并且可以通過(guò)當(dāng)前步驟存儲(chǔ)的狀態(tài)數(shù)據(jù)隨時(shí)重啟程序拄衰。
例如，下列計(jì)算階乘的程式為線性迭代過(guò)程：
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* product counter)
(+ counter 1)
max-count)))
解析后的計(jì)算過(guò)程如下圖：
樹(shù)形遞歸
樹(shù)形遞歸也是通過(guò)替換模型分析產(chǎn)生饵骨，樹(shù)形遞歸在一個(gè)表達(dá)式中會(huì)進(jìn)行多次遞歸調(diào)用翘悉，形成類(lèi)似樹(shù)形的遞歸計(jì)算過(guò)程，所以稱(chēng)為樹(shù)形遞歸過(guò)程居触，此過(guò)程的時(shí)間消耗是指數(shù)級(jí)的妖混，與樹(shù)形的節(jié)點(diǎn)呈正相關(guān)性，消耗的空間與樹(shù)的最大深度呈正相關(guān)性饼煞。
樹(shù)形遞歸存在大量的冗余計(jì)算源葫，因此它的計(jì)算效率并不高，但它描述及解決某些問(wèn)題更加直觀（例如繼承類(lèi)型的數(shù)據(jù)）砖瞧，所以它也是一種設(shè)計(jì)程序的重要工具息堂。
下列計(jì)算斐波那契數(shù)列的程度為樹(shù)形遞歸過(guò)程：
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
解析后的計(jì)算過(guò)程如下圖：
