遞迴是在函數中呼叫自己形成的，但是匿名函數沒有名字，要怎麼讓它遞迴？最近比較有空了，所以來試試看，也稍微練練手，究竟很久沒寫文。（其實是因為快被火了，就做到月底，所以現在給的任務比較少...）

先用階乘來做簡單的例子。

function test1() {
    console.log(fact(5));
    function fact(n) {
        return n < 2 ? 1 : n * fact(n-1);
    }
}
test1();//print 120

如果要把fact改成匿名函數的形式，需要做一些改造，讓它可以傳入一個函數參數，然後用這個它構成遞迴。在這之前，先把它咖喱化：

function test2() {
    console.log(fact()(5));
    function fact() {
        return function(n) {
            return n < 2 ? 1 : n * fact()(n-1);
        };
    }
}
test2();//print 120

沒問題的話，進行下一步改造：

function test3() {
    console.log(fact(fact)(5));
    function fact(fact) {
        return function(n) {
            return n < 2 ? 1 : n * fact(fact)(n-1);
        };
    }
}
test3();//print 120

這樣，在函數內就可以透過傳入的參數來遞迴。其實在函數內，參數名字不需要叫做fact：

function test4() {
    console.log(fact(fact)(5));
    function fact(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(x)(n-1);
        };
    }
}
test4();//print 120

但是外部呼叫函數時還是帶著fact，我們可以用另一個函數來處理來去掉對名字的依賴，這樣才真正可以變成匿名函數：

function test5() {
    console.log(Y(function(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(x)(n-1);
        };
    })(5));
    function Y(f) {
        return f(f);
    }
}
test5();//print 120

這樣，透過一個簡單的外部函數Y，就可以讓匿名函數也可以構成遞迴。現在問題是，在函數裡面還是留著x(x)，這跟我們一般寫遞迴函數的寫法不一樣。如果要盡量接近第一個例子，可以把處理過程也移進Y：

function test6() {
    console.log(Y(function(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(n-1);
        };
    })(5));
    function Y(f) {
        return function(x) {
            return x(x);
        }(function(x) {
            return f(function(n) {
                return x(x)(n);
            });
        });
    }
}
test6();//print 120

這個Y函數，聽說就是有名的Y Combinator，裡面的推導過程，可以參考良葛格的文章：Y Combinator，或是從Wiki看到的Javascript例子：The Y Combinator explained with JavaScript，我不學無術就不多廢話。

接下來才是我真正想做的東西，把Y Combinator用在Mutual Recursion...因為網路上找不到Javascript的例子，所以只好自己做。前面的過程是為了幫助自己理解，不然不知道怎改。

把Y函數擴充一下，讓它接受兩個參數，底下的結構也一併擴充，就可以讓兩個匿名函數互相呼叫構成遞迴，改名為Ys（據說可以做Mutual Recursion的叫做Y*）：

function test7() {
    console.log(Ys(function(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(n-1);
        };
    }, function(x) {
        return function(n) {
            return n < 2 ? 1 : n * x(n-1);
        };
    }));
    function Ys(f, g) {
        return function(x, y) {
            return x(y, x);
        }(function(x, y) {
            return f(function(n) {
                return x(y, x)(n);
            });
        }, function(x, y) {
            return g(function(n) {
                return x(y, x)(n);
            });
        });
    }
}
test7();//print 120

傳入的兩個函數其實完全一樣，好像看不出到底有沒有構成Mutual Recursion...反正先求會動，再求有用。

用另外一對函數來試試看：

function test8() {
    let fi = Ys(function(even) {
        return function(n) {
            if(n < 2) return 'odd';
            else return even(n-1);
        };
    }, function(odd) {
        return function(n) {
            if(n < 2) return 'even';
            else return odd(n-1);
        };
    });
    console.log(6, fi(6));
    console.log(7, fi(7));
    function Ys(f, g) {
        return function(x, y) {
            return x(y, x);
        }(function(x, y) {
            return f(function(n) {
                return x(y, x)(n);
            });
        }, function(x, y) {
            return g(function(n) {
                return x(y, x)(n);
            });
        });
    }
}
test8();
//print 6 even
//print 7 odd

看起來是對了。不過因為我需要的是先把函式庫內的特定函數處理過，之後再拿使用者提供的函數來互相遞迴，所以把它做一下咖喱化：

function test9() {
    let fi = Ys(function(even) {
        return function(n) {
            if(n < 2) return 'odd';
            else return even(n-1);
        };
    })(function(odd) {
        return function(n) {
            if(n < 2) return 'even';
            else return odd(n-1);
        };
    });
    console.log(6, fi(6));
    console.log(7, fi(7));
    function Ys(f) {
        return function(g) {
            return function(x) {
                return function(y) {
                    return x(y)(x);
                };
            }(function(x) {
                return function(y) {
                    return f(function(n) {
                        return x(y)(x)(n);
                    });
                };
            })(function(x) {
                return function(y) {
                    return g(function(n) {
                        return x(y)(x)(n);
                    });
                };
            });
        }
    }
}
test9();
//print 6 even
//print 7 odd

想要再酷炫一點，可以把Ys用arraw function改寫：

function test10() {
    let Ys = f=>g=>(x=>y=>x(y)(x))(x=>y=>f(n=>x(y)(x)(n)))(x=>y=>g(n=>x(y)(x)(n)));
    let fi = Ys(function(even) {
        return function(n) {
            if(n < 2) return 'odd';
            else return even(n-1);
        };
    })(function(odd) {
        return function(n) {
            if(n < 2) return 'even';
            else return odd(n-1);
        };
    });
    console.log(6, fi(6));
    console.log(7, fi(7));
}
test10();
//print 6 even
//print 7 odd

恩，改寫過就跟密碼差不多了XD

其實講到Mutual Recursion跟Y Combinator，會查到一篇文章：Many faces of the fixed-point combinator...但是我看不太懂（符號也不習慣？），所以只能試試自己硬幹...沒想到還可以動就是了XD