在网上搜来的用fun在shell中写递归的帖子,偶然发现下贴
大神原贴http://www.cnblogs.com/me-sa/archive/2012/04/28/2474892.html
贴中认为N*F(N-1)为尾递归,但我认为存在副作用,不应该算作尾递归
也可能是我对fun的理解有限…
因为原贴使用了数学理论,看起来不太亲民,拼了一天把原理弄通了(编程层面,不是底层执行层面)不知道是否有为此困扰的小伙伴,所以分享一下,不喜勿喷
shell中输入
y(M) ->
G = fun (F) -> M(fun(A) -> (F(F))(A) end) end,
G(G).
Fac = fun (F) ->
fun (0) -> 1;
(N) -> N * F(N-1)
end
end.
(y(Fac))(5).
120
因为将Fac作为参数传给了y,即M为Fac,而M的fun作为参数传递给了Fac,此处套用调用即揭开一层fun的想法,得到的结果是这样的
shell中输入
Fac = fun (F) ->
fun (0) -> 1;
(N) -> N * F(N-1)
end
end.
G = fun (F) -> Fac(fun(A) -> (F(F))(A) end) end,
(G(G))(5).
120
此处我想不到什么好办法表示Fac,在G调用Fac时Fac已经打开一层fun了
将fun(A) -> (F(F))(A) end作为参数传递给Fac后,和G合并成这个样子
shell中输入
G = fun (F) -> fun(0) -> 1;(N) -> N*(F(F))(N-1) end end.
(G(G))(5).
120
注意此处fun(A) -> (F(F))(A) end已经打开了
之后G将自己作为参数传递给了自己,打开了最后一层fun
此处代码已经不能执行了,但看到了一个有趣的调用
(G(G)) = fun(0) -> 1;(N) -> N * (G(G))(N-1) end.
将5带进去后,有了(G(G))5 = 5*(G(G))(4)
没错,递归了