匿名函数递迴

递迴是在函数中呼叫自己形成的，但是匿名函数没有名字，要怎么让它递迴？最近比较有空了，所以来试试看，也稍微练练手，究竟很久没写文。（其实是因为快被火了，就做到月底，所以现在给的任务比较少...）

先用阶乘来做简单的例子。

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