聲明：本文是作者在學習SICP有關過程抽象知識的理解，由於書中的語句有些晦澀，所以將作者的理解共享給大家希望幫助一些朋友。原書對尾遞歸並沒有太多介紹，但是這裡給出了詳細的解釋。
目前是凌晨1點48分。嗯，剛剛寫完這篇日志。忍不住想說點什麼，或許是當一個不好的書托。可能這些內容對於很多人來說是沒有用的，他們甚至會鄙視我寫的東西，覺得為這些東西花費時間不值得。對於這些人，我想說，每一個對計算機有著濃厚興趣的人，都有著一個想夠徹頭徹尾了解每天超過12小時面對的這台機器是如何工作的願望。像SICP和CSAPP這種書無疑是枯燥的，你可能一天看下來，仔細品讀的話只能看三四頁，但是如何你能夠真正理解這幾頁書的內涵的話，那麼收獲將是巨大的。從去年5月份，陳大師推薦我讀CSAPP之後，我才真正找到了那種看上去很枯燥，但是一讀起來就欲罷不能的書。這類的書讀起來都很困難，如果你帶著很強的功利性來讀的話，是不可能讀下去的。我想了想，能夠支撐我一天坐在那琢磨這幾頁書中說的核心意思的力量，就是來源於我真正想了解計算機是怎麼工作的，獲取這種信息對於我來說是非常快樂的，這種感覺是奇妙的。
函數一般是指數學上面的一種計算形式，偏向說明語句，描述如何根據給定的一個或者幾個參數去計算出一個值。如SICP中關於求一個數的平方根的函數，我們在該函數的說明中可以推斷出關於平方根的一些具體性質和一般性的事實，但是我們無從得知計算一個數的平方根的具體方法。你可能會說，求平方根不就是開根號麼。可是你有沒有想過，[開根號]也僅僅是一個說明性的語句，具體怎麼計算你還是不知道的。延伸到計算機當中的函數，其實和數學上面的函數意義是相同的，我們只不過是換成高級程序設計語言來寫我們對於一個函數一般性事實的說明，實際上我們並沒有給出一個具體的計算過程。比如求平方根，如果我們是調用math.h中的庫函數來求的話：sqrt(x*1.0)，這種形式只是一個說明型的語句，我們利用這個語句來指導計算機去計算，但實際上這個函數並沒有提供具體的計算過程。計算機當中的解釋器就負責把這種說明性語句轉化成真正的計算過程(期待到時候寫一個解釋器哇)。
其實感覺這兩者的區別就和寫作文一樣，一個是提綱，另外一個是具體的內容。
SICP中關於求一個數平方根的問題，使用的是牛頓的逐步逼近法則，不斷的去求新的猜測值，直到結果滿足一定的精度結束。求平方根是一個大的功能，想要完成這個大的功能還需要一些小的功能來輔助。
過程抽象的實質就是一種功能的分解
我們把整個一個大的計算過程分為幾個部分，每一個部分都能單獨完成其中的一個小功能，他們組合起來又能夠完成最終的功能。所謂過程的抽象和C++中的面向對象思想是和相像的，沒准都是一個東西，我不太確定，但是過程的抽象說的都是一個意思，就是對創造者來說重要的是過程的實現，而對於使用者來說，過程的抽象可以屏蔽掉內部實現的細節，從而減輕使用者的負擔，只關心這個過程的『黑盒』能夠做什麼。所以這樣一來就增加了程序局部的可替換性，因為對於實現一個功能來說，過程的內部實現可以多種多樣。
大家都知道調用函數或者過程的時候，有的時候需要傳遞一些合適的參數，在調用的過程中，函數的形式參數的名字對我們來說其實並不重要，相對於使用者來說確實是這樣。但是對於過程的設計者來說，形式參數的名字，或者說是局部變量的名字，對於整個過程能夠正常的執行就非常重要了。這也是過程抽象當中的一個細節，計算機把一些復雜的東西封裝到了內部。
關於過程的抽象中可能會有兩個新的概念，約束變量和自由變量。單就一個過程來講，我的理解是約束變量就是一種名字是什麼無所謂，但是統一換名之後不改變過程意義的一種變量，他有自己的作用域，類比於局部變量吧。而自由變量就類比於全局變量，或者靜態變量，我是這麼理解的。約束變量的名字並不重要，重要的是哪些地方用了同一個約束變量。
為什麼說約束變量的名字對於過程的執行是非常重要的呢。很直接的一個理解就是：局部變量可以在作用域內可以屏蔽同名的全局變量，類比一下，約束變量在相應的作用域內會屏蔽同名的自由變量。
(define (good-enough? guess x)
((abs (- (square guess) x)) 0.001))
舉例來講，在上面這個過程中，guess 和 x 是good-enough?這個過程的兩個約束變量，<, abs, -, square都是自由變量。自由變量是和環境相關的，他們已經有了確定的意義來保持他們正常的執行，但是如果現在guess這個約束變量改名為abs，將會導致abs這個自由變量的意義被約束變量屏蔽，過程中出現的abs為約束變量，不在具有自由變量當中求絕對值的功能。
所以說，對於過程的設計者而言，過程實現中，自由變量和約束變量的名字都在哪些地方用到是一個非常需要注意的地方，一個過程的順利執行依賴於約束變量和自由變量的名字不同，並且自由變量的意義正確。
這一點的抽象就更加為我們過程的使用者考慮，它也是一種局部的概念，像局部變量一樣，只有內部的作用域可以訪問並且識別他，作用域之外是不知道作用域內有這個東西的。只不過我們之前抽象的是變量，這次抽象的是過程。
sicp中的求平方根的過程，和用戶交互的僅僅是一個接口sqrt，其中的子過程的具體實現細節都被抽象一個個的【黑箱】。但是對於用戶來說，這些實現計算過程的黑箱是沒有用的，只會擾亂他們的思維，並且在用戶想自定義一個與這些黑箱中的某一個同名的過程的時候是不被允許的（不能在一個作用域內定義兩個同名的過程），這些有著具體功能的【黑箱】污染了全局名字環境。
對於一個結構局部的東西，我們更好的方式是把他們定義在這個結構的內部，而不應該放在全局環境范圍內，因為你需要的並不是其他人也需要的，如果其他人不需要這些東西，那麼他們的命名就有可能造成過程調用的命名沖突，造成程序混亂。
scheme支持在過程的內部再定義新的過程，內部新定義的過程只能在內部作用域可見，外部是不知道有內部這些過程的定義的。
(define (sqrt x)
(define (good-enough? guess x)
(abs (- (square guess) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough? guess x) guess
(sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x))
根據上面的例子來看，我們就把求平方根這計算過程中用到的小黑箱一個一個的都定義在了這個過程的內部 ，過程之外看不到他們，這種嵌套的過程定義就叫做塊結構。局部化使程序更清晰,減少全局名字,減少相互干擾。除此之外，由於將一些黑箱進行了內部定義之後，還有一處可以改進的地方，就是參數x的使用。由於局部過程的形參都在x的作用域內，我們就不必在局部過程中再傳遞x了，直接調用即可。相對於局部過程來說，現在的X由原來的約束變量，變為現在的自由變量了。
我們可以用不同種類的過程來完成同一件任務，那麼在真正的程序設計的時候，我們應該選用哪種方式呢？按照之前數據結構的角度來看，我們有兩個指標：時間復雜度和空間復雜度。不同的過程自然有這不同的計算過程，我們應該通過衡量兩個不同計算過程的上述的兩個指標來確定最終選擇哪一個作為最終版本。這就要求我們能夠准確的觀察到任何一個過程執行的過程和執行的效果，以及執行過程中所耗費的各種資源。
遞歸和迭代應該是兩種非常重要的計算形式。如果一個問題同時可以用這樣兩種形式解決，那麼我們應該選擇哪一種呢？
在以實例說明遞歸和迭代的區別之前，首先要明確這樣兩個概念的區別：
遞歸計算進程:是計算中的情況和具體的執行行為,反映計算中需要耗費資源維持的過程執行的某些信息和情況。 用遞歸方式定義過程：是程序寫法,在定義過程的代碼裡出現了對這個過程本身的調用，但是實際的計算過程可能並不需要耗費資源來進行維持過程的執行情況。
假如現在有一個求n的階乘的需求：我們有正向和逆向兩種思路來求得結果
算法如下：n! = n (n-1)! = n (n-1) (n-2)!…..2 1 = n * (n-1)!
有了具體的計算進程，我們可以根據它來寫一個過程
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
PS:可以看出這個過程在定義的時候調用了自身
假設現在我們想計算（factorial 6），根據shceme的代換模型推導，可以得出如下計算進程圖示：
從圖示中我們可以看出，當我們計算（factorial 6）的時候，根據計算過程的定義，要執行(* 6 (factorial (- 6 1)))。通過這一個復合的表達式我們就可以看出來，（factorial 6）這一步的計算結果並沒有計算出來，它需要計算下一個狀態來輔助它得出（factorial 6）這一步的計算結果。因為本次的計算沒有完成要進行其他的運算來輔助完成，那麼本次的運算就算是中斷了，既然中斷了，我們就需要保存現場，保存此次計算過程目前的狀態（變量等等一些資源）以便當下一狀態的計算結果出來之後能夠順利的銜接上，從而計算出最終的結果。以後的計算進程仍然是按照這種形式來的，直到遇到邊界。
到此為止，我們就知道，這個計算進程是一個遞歸計算進程，因為他在計算的進程當中需要耗費資源來保存所需的一些情況和信息。遞歸的計算過程，想必大家都很熟悉，它是屬於一種推遲求值的方式，不能夠立即求出最���結果，每一次的計算都依賴於它的子計算狀態，直到遇到邊界之後，才逐層返回計算結果，最終返回到起點，求出結果。可以說，遞歸是從後向前推的過程，計算最後一步，也就是最終結果，也許就會需要倒數第一步的結果，那麼就計算倒數第一步，以此類推，直到計算到第一步的時候，利用題設條件可以得到第一步的最終結果，然後再把計算結果逐層返回到起點，也就是計算最後一步的位置，得到最終結果。（是深度優先搜索的道理）但是如果計算的次數太多，迭代的層數太深，留給過程的棧空間很有可能會溢出，造成爆棧。
那麼，根據上面的時間和空間復雜度兩個指標，我們將評判這個用遞歸計算階乘的計算進程的好壞。（其實計算進程就是算法，有木有？！）
我們可以看到，如果n是6，那麼一共要計算12次，如果n是5那麼要計算10次，所以相應的時間復雜度大致可以估算為O(N)。從（factorial 6）遞歸到邊界最低端的時候，一共進行了6次迭代，隨著n的增加，遞歸的次數會隨n線性增長，所需的內存空間也會線性增長。所以控件復雜度應為O(N)。
綜上所述，整個遞歸計算進程已經評價完畢，准確的說，這是一個線性遞歸計算進程。
算法：n!就是從1開始一直累乘到n，最終的累乘結果等於n!
根據這個算法，寫出一個過程如下
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if ( counter max-count) product
(fact-iter (* counter product) (+ counter 1)
max-count)))
從上述的過程我們可以看出，它在定義的時候，也是調用了自身。計算（factorial 6）的進算進程圖示如下：
根據圖示可以看出，每一次的計算狀態由三個變量來維持，而且每一個狀態的計算和其他狀態的計算是獨立的，各自狀態的計算結果不依賴於其他的狀態。每一次狀態的計算都是干脆利落的執行，下一個狀態計算所需要的資源通過參數傳遞，上一個狀態計算完成之後就沒有任何用處了，它不必為前一個或者後一個狀態來保存什麼有用的信息，需要的信息都根據參數傳遞給新的狀態了。而且，在不斷計算的過程中，由於把所需要的值的信息一直作為參數傳遞，一旦得出了最終的結果，不用像遞歸一樣，把計算結果返回給上一個狀態，而是直接返回給一開始的調用者。過程的調用都是在棧空間來開辟內存的，根據以上計算特點，上一個狀態計算結束之後可以立即銷毀之前所用的棧空間，避免了棧溢出。
這樣的計算進程，很容易就可以看出來，時間復雜度O(N)，空間復雜度，因為每次計算只需要保存三個變量，它不隨n的變化而變化，則為O（1）,常量級。不僅僅是這個計算過程這樣，計算機當中所有的計算的空間復雜度都應該在常數級別下完成，因為內存空間是有限的。
上述計算進程被稱為迭代，如果單就這個實例來說，應該是線性迭代進程。
一般的編程語言都是通過循環等一些復雜的結構來描述迭代的，但是在scheme中卻可以用遞歸的形式來描述迭代。
觀察上面兩個求階乘的過程，我們可以看到。雖然兩者都是調用了自身，用了遞歸的形式來定義整個過程，表面上都屬於遞歸調用，但是，『遞歸』版本中，在最後的遞歸調用之後，還需要進行乘n的操作才算作是完成了此次計算，而在 [迭代]版本中，遞歸的調用屬於最後一個方法，末尾的遞歸調用執行完，此次的計算也就執行完了，屬於該過程的最後一個操作，這就是”尾遞歸”。尾遞歸相對於正常的遞歸來說，它的遞歸調用處於過程最後，之前過程計算積累的信息對於接下來的這次遞歸調用的最終結果沒有任何影響，那麼本次過程調用存儲在棧內的信息就可以完全清除。把空間留給之後的遞歸過程使用。所以說，這意味著如果使用尾遞歸的方式，是可以實現無限遞歸的。
尾遞歸的本質，其實是將遞歸方法中的需要的“所有狀態”通過方法的參數傳入下一次調用中。這樣上一次的調用就不用再保存一些額外的信息，並且在計算到邊界的時候，因為計算的結果一直在累積，所以計算到終點的時候，也就得到的最後的結果，可以直接返回給最開始調用這個方法的調用者。
至於把正常遞歸轉化為尾遞歸的方法，我覺得比較直接的做法就是，正常遞歸是從後向前考慮，如果寫尾遞歸，那麼就把問題從前向後考慮，並且把所需的信息當做參數傳遞。
一般來講，雖然在過程定義上，看起來是遞歸的，但是實際的計算進程的原理有可能是迭代的，也有可能是遞歸的，因為，迭代的計算是可以用尾遞歸來進行定義的。
