5.1. 高效地实现递归¶

接下来我们考虑如何在 SLang 2 中实现递归函数。在 λ-演算和 SLang 1 中，所有函数都是匿名的，不能调用自身。我们可以使用不动点组合子， 例如 \(Y\) 组合子。

let
     Y = fn (h) => (fn (x) => (h (x x)) fn (x) => (h (x x)))
     f = fn (g) => fn (n) => if (n === 0) then 1 else (n * (g (n - 1)))
in
     ((Y f) 5)
end

这种做法的问题是什么？

在 SLang 2 中，我们可以利用引用和赋值语句，用一种称为“打结” （tying the knot）的技术高效地实现递归。

为了体会这种技术的工作原理，请想一想下面这个程序的值是多少？

let
     dummyClosure = fn (n) => (n + 1)
in
     let
           f = fn (n) => if (n===0) then 1 else (n * (dummyClosure (n - 1)))
     in
           (f 5)
     end
end

我们怎样才能修改这个程序，把上面的函数 f 变成我们熟知的名字为 factorial 的（递归）函数，从而使上面程序的值变为 120？

提示：添加一条赋值语句，但该添加哪一条？添加在哪里？回答这些 问题，你就会明白为什么这种技术被称为“打结”。

5.2. 练习 TTK¶

下面的问题将帮助你熟悉 TTK 技术。要获得这道题的学分，你必须 连续三次正确完成这个随机化问题。

提交答案时，请记住给出完整的指称值，例如 [ "Num", 0 ] ，而 不只是 0 。