匿名函数也就是不需要取名的函数。函数递归指的是函数通过引用自己的名字调用自身。匿名函数没有名字怎样才能递归呢？

匿名函数

匿名函数（lambda，$\lambda$），作为函数式编程的基本元素，已经被越来越多的语言支持。

比如 C# 中是这样编写匿名函数的

1
var f = x => x + 1;

JavaScript 中是这样编写匿名函数的

1
var f = x => x + 1;

咦，居然是一样的，里面莫非有什么 PY 交易？

匿名递归

最典型的递归函数是阶乘函数。
$$
f(n) =
\begin{cases}
1, & n \le 1 \
n*f(n-1), & n \gt 1
\end{cases}
$$
翻译成 JavaScript 

1
2
3
var f = function(n){
  return n <= 1 ? 1 : n * f(n - 1);
}

这是一个递归，但不是一个真正意义上的匿名递归函数。因为函数名为 f 而且函数体中的 f(n-1) 引用了自身的名字。

通常递归函数需要引用自身的名字来调用自身达到递归的效果。

匿名函数没有名字，没办法这么做。

这么想想递归匿名函数似乎是不可能的。

但其实是可以做到的。

看下面的这个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
(function(f){
	return (function(g){
		return g(g);
	})(function(h){
		return function(x){
			return f(h(h))(x);
		};
	});
})(function(self){
  return function(n){
    return n <= 1 ? 1 : n * self(n - 1);
  };
});

测试调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
(function(f){
	return (function(g){
		return g(g);
	})(function(h){
		return function(x){
			return f(h(h))(x);
		};
	});
})(function(self){
  return function(n){
    return n <= 1 ? 1 : n * self(n - 1);
  };
})(1);
// => 1
(function(f){
	return (function(g){
		return g(g);
	})(function(h){
		return function(x){
			return f(h(h))(x);
		};
	});
})(function(self){
  return function(n){
    return n <= 1 ? 1 : n * self(n - 1);
  };
})(3);
// => 6

这个函数就是阶乘函数的匿名递归版。里面用到了 Y 组合子 。

推导过程

来龙去脉