說到生成函數操作上應注意的事項，首重『表達式』之『所指』、『虛名變數』的『替換』，以及『初始資料』的『應用』。通熟 λ 表達式 α 變換者，想必知之深矣。

於此再度回顧一下變元的『替換規則』的定義︰

是指將 『表達式』中所有『自由出現』的『 變元』，都使用 『表達項』來取代。我們可以歸納的定義如下︰

是所指 表達式的任意變元
是所指 表達式的任意構成項── 該式在建構過程中的各個合乎語法的子表達式 ──。

一、

二、 ，只要 變元不是 變元

三、

四、

五、 ，只要 變元不是 變元

假使有一個簡單的函式 ，它不包含著其它『子函式』以及『函式應用』，當我們說『』是指 是由上面的變元『替換規則』從   得到的。這時我們講 是經由『 變換』從 變更『受約束變元 』成為 『受約束變元 』而得來。為什麼那一邊說著『自由的』，這一邊又講著『受約束』？是因為 表達式中 變元是『自由的』，『抽象封裝』成為『函式』，這時那個  變元就成『受約束』的了。其次為何要先『限定簡單』的函式呢？如果看一看 的表達式， 那麼我們又要如何替換它呢？人們之所以需要『重新命名』受約束變元，是因為『應用化約』可能產生的『命名衝突』，或許『直覺』上講又怎麽會去用了『 變換』以後，卻反而又製造了『新的衝突』的呢？因此與其將它『一碼歸一碼』的煩雜分解的說，不如就建立某些『不成文的規矩』，每當提到受約束的變元『重新命名』時，就是說使用從來『不曾出現』或者說『不起衝突』的新的變元名字的意思！這樣不管再複雜的表達式都可以用著『 變換』『一步一步』的『系統化』轉換成另一個同等的表達式，於是我們可以說︰

。再者，與『函式所約束之虛名變元』無關的『自由變元』一般都來自於『函式應用』 ── 比方 的『輸入項』 變元 ──，通常除非為了表達清晰起見，人們不會『重新命名』輸入項。如果從『程式計算』的角度講，『計算資料』是程式外部來的，在程式裡當然要叫它什麼名字都可以。於是那個『系統化』的『更名』辦法，自然可以行使於任何『函式』或者『應用』的『子函式表達項』中，也許就不會再有『表達轉換』作法上彼此之歧見的了！！

假使再次細思『 λ 表達式』的歸納定義，最簡單的表達式『始於變元』，然後方在其上建立『函式』，之後才『應用』函式於『變元』之上。因此前面說的那個簡單的函式 的可能構成是極其有限的，比方說 中只能有一個變元，假使 有兩個以上的變元，那一定是由『函式應用』或者『多元函式』 所產生的。所以它只可能像是 或者 這樣。也許有人會想難道它不能是像 或者 的嗎？在某些『應用 λ語言』中，這種語法是合宜的；然而這裡用的卻是『純粹』Pure 的 λ語法，這個『語法集』中根本沒有『什麼是 或 』，因此表達所需要用的一切都得在『基元』Primitive 上自己建立。『複雜』與『難題』是兩種不同的『困難性』。許多『難題』表述起來很簡單── 比方說費瑪最後定理︰ 沒有整數解 ──，想解決卻十分困難。而『複雜』是源於構成『部份』眾多或者『結構』縱橫多層，雖然基本『單元』並不『困難』，基礎結構『組件』也很『簡單』，由於『數大層多就是難』這就是 λ 表達式的『寫照』。這個『複雜性』或許也就是『 λ 語法』之所以『方言』崛起的緣故。

─── 摘自《λ 運算︰概念導引《三》》

 

因此明白若是 ，則

。

如果已知 ，那麼也

 

且讓我們用曾講過的費波那契序列公式︰

……

為什麼數學上常常要用『遞迴定義』的呢？假使你出於『好玩』，想『定義』一個『數列』，那麼有什麼『簡單』的辦法的呢？

有人說︰這很簡單啊！就給一個 『公式』Formula 就好了，就好比講這個數列是

。

有人問︰萬一你不知道『那個公式』呢？還是說如果『公式不存在』這樣子就根本『沒辦法』去定義『數列』的呢？

有人答︰『可以』的啊！比方說假使你『知道』

一、 的『值』

二、曉得如何從 『計算』出 的『值』，這樣就算是不知道 是能不能夠表達，一樣可以『定義』這個『數列』的啊！

據說義大利的數學家李奧納多‧費波那契 Leonardo Fibonacci 描述各代『兔子生育』總數目時得到這個數列︰

因此 ，所以可以逐步的得到『費波那契數列』。當然可以求解那一個『差分方程式』得到

。

然而並非所有可以『遞迴定義』的數列，都能有『公式解』，或者說還沒將它『算出來』。所以能這樣從幾個『初始資料』和一個『遞迴關係』來定義東西的方式，自然有它的好處的了。

─── 摘自《λ 運算︰計物數《遞迴補遺》》

 

談談這個推導過程。假設

，從遞迴關係可得

如果 是 的兩個根，而且 ，也就是說 ，那麼 可改寫為

，所以

。