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

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

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

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

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

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

; 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);
    }
}    

上面的階乘算法比較直觀，這里就不再進行解釋了。重申下我們要探究的問題

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

解決一個新問題，常見的做法就是類比之前解決的問題。我們要解決的這個問題和求解下面的等式很類似：

2x = x + 1

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

但是我們的問題比這個要復(fù)雜些了，因為我們這里需要用if、n、*、-這四個符號來表示FACT，可以這么類比是因為一個程序無非就是通過一些具有特定語意的符號（編程語言規(guī)定）構(gòu)成的。

再進一步思考，FACT 需要用四個符號來表示，這和我們求解多元方程組的解不是很像嘛：

x + y = 3
x - y = 1

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

x = 3 - y
y = x - 1

即

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

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

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

FACT = F (FACT)

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

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

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

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

這里直接給出FACT對應(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);
        }
  }
}

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

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

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

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

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

可以看到，我們在求出(FACT n)時完全沒有用到初始的g，換句話說就是g的取值不影響我們計算(FACT n)。
那么我們完全可以這么定義FACT：

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

可惜，我們不能這么寫，我們必須想個辦法表示無窮。在函數(shù)式編程中，最簡單的無窮循環(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 算子的嚴格推導(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解釋器中運行，因為就像上面說的，這其實是個死循環(huán)，如果你把上面代碼拷貝到解釋器中運行，一般可以得到下面的錯：

RangeError: Maximum call stack size exceeded

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

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

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

舉個簡單的例子：

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

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

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

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

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

var lazy_p = function() { return p; }

這時如果想得到p的值，就需要(lazy_p)才可以得到了。基于這個原理，下面給出最終版本的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解釋器中運行FACT了，可以看到，這里面沒有使用函數(shù)名也實現(xiàn)了遞歸方式求階乘。
本文一開始給出的FACT版本在解釋器內(nèi)部也會轉(zhuǎn)換為這種形式，這也就解釋了本文所提出的問題。

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

最后，希望這篇文章對大家理解編程語言有一些幫助。有什么不對的地方請留言指出。