摘要：如果存在這么個(gè)函數(shù)，那么我們就可以通過(guò)求解的不動(dòng)點(diǎn)來(lái)求出了。尋找轉(zhuǎn)換函數(shù)的不動(dòng)點(diǎn)找到了轉(zhuǎn)換函數(shù)后，下一步就是確定其不動(dòng)點(diǎn)了，而這個(gè)不動(dòng)點(diǎn)就是我們最終想要的。

本文原發(fā)于個(gè)人博客

遞歸 作為計(jì)算機(jī)科學(xué)中很重要的一個(gè)概念，應(yīng)用范圍非常廣泛。比較重要的數(shù)據(jù)結(jié)構(gòu)，像樹(shù)、圖，本身就是遞歸定義的。
比較常見(jiàn)的遞歸算法有階乘、斐波那契數(shù)等，它們都是在定義函數(shù)的同時(shí)又引用本身，對(duì)于初學(xué)者來(lái)說(shuō)也比較好理解，但是如果你對(duì)編程語(yǔ)言，特別是函數(shù)式語(yǔ)言，有所研究，可能就會(huì)有下面的疑問(wèn)：

一個(gè)函數(shù)在還沒(méi)有定義完整時(shí)，為什么能夠直接調(diào)用的呢？

這篇文章主要是解答上面這個(gè)問(wèn)題。閱讀下面的內(nèi)容，你需要有些函數(shù)式編程的經(jīng)驗(yàn)，為了保證你能夠比較愉快的閱讀本文，你至少能看懂前綴表達(dá)式。相信讀完本文后，你將會(huì)對(duì)編程語(yǔ)言有一全新的認(rèn)識(shí)。
本文所有演示代碼有Scheme、JS兩個(gè)版本。

下面的講解以階乘為例子：

; Scheme
(define (FACT n)
  (if (= n 0)
    1
    (* n (FACT (- n 1)))))

; JS
var FACT = function(n) {
    if (n == 0) {
        return 1;
    } else {
        return n * FACT(n-1);
    }
}    

上面的階乘算法比較直觀(guān)，這里就不再進(jìn)行解釋了。重申下我們要探究的問(wèn)題

FACT 這個(gè)函數(shù)為什么在沒(méi)有被定義完整時(shí)，就可以調(diào)用了。

解決一個(gè)新問(wèn)題，常見(jiàn)的做法就是類(lèi)比之前解決的問(wèn)題。我們要解決的這個(gè)問(wèn)題和求解下面的等式很類(lèi)似：

2x = x + 1

在等號(hào)兩邊都出現(xiàn)了x，要想解決這個(gè)問(wèn)題，最簡(jiǎn)單的方式就是將等號(hào)右邊的x移到左邊即可。這樣就知道x是什么值了。

但是我們的問(wèn)題比這個(gè)要復(fù)雜些了，因?yàn)槲覀冞@里需要用if、n、*、-這四個(gè)符號(hào)來(lái)表示FACT，可以這么類(lèi)比是因?yàn)橐粋€(gè)程序無(wú)非就是通過(guò)一些具有特定語(yǔ)意的符號(hào)（編程語(yǔ)言規(guī)定）構(gòu)成的。

再進(jìn)一步思考，FACT 需要用四個(gè)符號(hào)來(lái)表示，這和我們求解多元方程組的解不是很像嘛：

x + y = 3
x - y = 1

為了求解上面方程組，一般可以轉(zhuǎn)為下面的形式：

x = 3 - y
y = x - 1

即

(x, y) = T (x, y)

其中的T為一個(gè)轉(zhuǎn)換，在線(xiàn)性代數(shù)其實(shí)就是個(gè)矩陣，根據(jù)矩陣T的一些性質(zhì)，我們可以判定(x ,y)是否有解，以及解的個(gè)數(shù)。

對(duì)比此，我們可以把問(wèn)題轉(zhuǎn)化為下面的形式：

FACT = F (FACT)

上面的F為某種轉(zhuǎn)換，在這里其實(shí)就是個(gè)需要一個(gè)函數(shù)作為參數(shù)并且返回一個(gè)函數(shù)的函數(shù)。如果存在這么個(gè)F函數(shù)，那么我們就可以通過(guò)求解F的不動(dòng)點(diǎn)來(lái)求出FACT了。

但這里有個(gè)問(wèn)題，即便我們知道了F的存在，我們也無(wú)法確定其是否存在不動(dòng)點(diǎn)，以及如果存在，不動(dòng)點(diǎn)的個(gè)數(shù)又是多少？

計(jì)算機(jī)科學(xué)并不像數(shù)學(xué)領(lǐng)域有那么多可以套用的定理。

證明F是否存在是個(gè)比較難的問(wèn)題，不在本文的討論范圍內(nèi)，這涉及到Denotational semantics領(lǐng)域的知識(shí)，感興趣的讀者可以自己去網(wǎng)上查找相關(guān)資料。

這里直接給出FACT對(duì)應(yīng)的函數(shù)F的定義：

; Scheme
(define F
  (lambda (g)
    (lambda (n)
      (if (= n 0)
        1
        (* n (g (- n 1)))))))

; JS
var F = function(g) {
    return function(n) {
        if (n == 0) {
            return 1;
        } else {
            return x * g(n-1);
        }
  }
}

可以看到，對(duì)比遞歸版本的FACT變動(dòng)不大，就是把函數(shù)內(nèi)FACT的調(diào)用換成了參數(shù)g而已，其實(shí)我們常見(jiàn)的遞歸算法都可以這么做。

找到了轉(zhuǎn)換函數(shù)F后，下一步就是確定其不動(dòng)點(diǎn)了，而這個(gè)不動(dòng)點(diǎn)就是我們最終想要的FACT。

FACT = (F (F (F ...... (F FACT) ...... )))

假設(shè)我們已經(jīng)知道了FACT非遞歸版本了，記為g，那么

E0 = (F g)      這時(shí)(E0 0) 對(duì)應(yīng) (FACT 0)得值，這時(shí)用不到 g
E1 = (F E0)     這時(shí)(E1 0)、(E1 1)分別對(duì)應(yīng)(FACT 0)、(FACT 1)的值
E2 = (F E1)     這時(shí)(E2 0)、(E2 1)、(E2 2)分別對(duì)應(yīng)(FACT 0)、(FACT 1)、(FACT 2)的值
.....
En = (F En-1)   這時(shí)....(En n)分別對(duì)應(yīng).... (FACT n)的值

可以看到，我們?cè)谇蟪?b>(FACT n)時(shí)完全沒(méi)有用到初始的g，換句話(huà)說(shuō)就是g的取值不影響我們計(jì)算(FACT n)。
那么我們完全可以這么定義FACT：

FACT = (F (F (F ...... (F 1) ...... )))

可惜，我們不能這么寫(xiě)，我們必須想個(gè)辦法表示無(wú)窮。在函數(shù)式編程中，最簡(jiǎn)單的無(wú)窮循環(huán)是：

; Scheme
((lambda (x) (x x))
  (lambda (x) (x x)))

; JS
(function (x) {
    return x(x);
})(function(x) {
    return x(x);
});

基于此，我們就得到函數(shù)式編程中一重要概念 Y 算子，關(guān)于 Y 算子的嚴(yán)格推導(dǎo)，可以在參考這篇文章 The Y combinator (Slight Return)，這里直接給出：

; Scheme
(define Y
  (lambda (f)
    ((lambda (x) (f (x x))
      (lambda (x) (f (x x)))))))

(define FACT (Y F))

; JS
var Y = function(f) {
    return (function(x) {
        return f(x(x));
    })(function(x) {
        return f(x(x));
    });
}
var FACT = Y(F);

這樣我們就得到的FACT了，但這里得到的FACT并不能在Scheme或JS解釋器中運(yùn)行，因?yàn)榫拖裆厦嬲f(shuō)的，這其實(shí)是個(gè)死循環(huán)，如果你把上面代碼拷貝到解釋器中運(yùn)行，一般可以得到下面的錯(cuò)：

RangeError: Maximum call stack size exceeded

為了得到能夠在Scheme或JS解釋器中可以運(yùn)行的代碼，這里需要解釋復(fù)合函數(shù)在調(diào)用時(shí)傳入?yún)?shù)的兩種求值策略：

正則序（Normal Order），完全展開(kāi)而后歸約求值。惰性求值的語(yǔ)言采用這種順序。

應(yīng)用序（Applicative Order），先對(duì)參數(shù)求值而后應(yīng)用。我們常用的大部分語(yǔ)言都采用應(yīng)用序。

舉個(gè)簡(jiǎn)單的例子：

var p = function() {
    return (p);
}
var test = function(x, y) {
    if(x == 0) {
        return 0;
    } else {
        return y;
    }
}
test(0, (p));

上面這個(gè)例子，采用應(yīng)用序的語(yǔ)言會(huì)產(chǎn)生死循環(huán)；而采用正則序的語(yǔ)言可以正常返回0，因?yàn)?b>test的第二個(gè)參數(shù)只有在x不等于0時(shí)才會(huì)去求值。

我們上面給出的var FACT = Y(F)在正則序的語(yǔ)言中是可行的，因?yàn)?b>Y(F)中的返回值只有在真正需要時(shí)才進(jìn)行求值，而在F中，n等于0時(shí)是不需要對(duì)g(n-1)進(jìn)行求值的，所以這時(shí)Y(F)(5)就能夠正常返回120了。

如果你覺(jué)得上面這段話(huà)很繞，一時(shí)不能理解，這樣很正常，我也是花了很久才弄明白，你可以多找些惰性求值的文章看看。

為了能夠得出在應(yīng)用序語(yǔ)言可用的FACT，我們需要對(duì)上面的Y做進(jìn)一步處理。思路也很簡(jiǎn)單，為了不立即求值表達(dá)式，我們可以在其外部包一層函數(shù)，假設(shè)這里有個(gè)表達(dá)式p：

var lazy_p = function() { return p; }

這時(shí)如果想得到p的值，就需要(lazy_p)才可以得到了?；谶@個(gè)原理，下面給出最終版本的Y 算子：

; Scheme
(define Y
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

(define FACT (Y F))
(FACT 5)   ;===> 120

; JS
 var Y = function(f) {
     return function(x) {
         return x(x)
     }(function (x) {
         return f(function(y) {
             return x(x)(y)
         })
     })
 }
 var FACT = Y(F)
 FACT(5)   ;===> 120

好了，到現(xiàn)在為止，我們已經(jīng)得到了可以在Scheme或JS解釋器中運(yùn)行FACT了，可以看到，這里面沒(méi)有使用函數(shù)名也實(shí)現(xiàn)了遞歸方式求階乘。
本文一開(kāi)始給出的FACT版本在解釋器內(nèi)部也會(huì)轉(zhuǎn)換為這種形式，這也就解釋了本文所提出的問(wèn)題。

本文大部分內(nèi)容由 SICP 4.1 小節(jié)延伸而來(lái)，寫(xiě)的相對(duì)比較粗糙，很多點(diǎn)都沒(méi)有展開(kāi)講的原因是我自己也還沒(méi)理解透徹，為了不誤導(dǎo)大家，所以這里就省略了（后面理解的更深刻后再來(lái)填坑?）。希望感興趣的讀者能夠自己去搜索相應(yīng)知識(shí)點(diǎn)，相信肯定會(huì)受益匪淺。

最后，希望這篇文章對(duì)大家理解編程語(yǔ)言有一些幫助。有什么不對(duì)的地方請(qǐng)留言指出。