函数式编程，递归游戏状态循环

Question

我计划编写一个简单的游戏来测试我对函数式编程的理解。使用函数式编程方式进行主循环的方法是通过递归实现，但是随着生成更多的堆栈帧，这样做会消耗更多的内存，对吗？

谢谢。

以下是来自如何在没有可变状态的情况下执行任何有用操作？的示例。

// imperative version
pacman = new pacman(0, 0)
while true
    if key = UP then pacman.y++
    elif key = DOWN then pacman.y--
    elif key = LEFT then pacman.x--
    elif key = UP then pacman.x++
    render(pacman)

// functional version
let rec loop pacman =
    render(pacman)
    let x, y = switch(key)
        case LEFT: pacman.x - 1, pacman.y
        case RIGHT: pacman.x + 1, pacman.y
        case UP: pacman.x, pacman.y - 1
        case DOWN: pacman.x, pacman.y + 1
    loop(new pacman(x, y))

- Peter

---

你使用的是哪种函数式编程语言？ - PriestVallon

Clojure，但如果取决于语言，我也很想知道F#。 - Peter

Answer 1

你已经使用尾递归实现了loop函数，即对loop的递归调用是函数中的最后一件事。这使得编译器/解释器（取决于语言）可以立即弹出当前堆栈帧并替换为递归调用的帧。

简而言之，以你的方式实现，不会发生堆栈溢出，并且loop可以运行所需的时间。

- waldrumpus

---

有关此内容的进一步阅读，请参阅http://en.wikipedia.org/wiki/Continuation-passing_style - Darius

好的，那么这可以假定在大多数语言中发生（即使是命令式语言）？ 如果递归调用不是最后一件事，我还有其他的方法吗？ - Peter

@Peter 这种优化通常不适用于命令式语言。Clojure也不执行此操作，但作为替代方案，Clojure提供了recur表单，您可以使用它来递归而不消耗堆栈空间（recur只能在尾部位置使用）。如果递归调用不在尾部位置，则只能通过重写它使其处于尾部位置来避免消耗堆栈空间（请注意，如果您无法轻松地这样做，那么您也无法轻松地将逻辑表示为循环而没有显式堆栈）。 - sepp2k

@Peter 重要的是调用者在调用被调用者后必须立即返回。类似这样的尾递归也可以：if x then loop(...) else loop(...)；但不包括这种情况：if x then (loop(...); 17) else loop(...)。 - waldrumpus

Answer 2

递归是新的迭代 :) 博客插件: http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

你说你正在使用Clojure，也很想知道F#的情况。

事实证明，基于JVM的语言（Java、Scala、Clojure等）无法在VM级别上支持尾调用优化，因此需要像Clojure的recur这样的解决方案。基于CLR的语言（F#、C#、VB等）可以并且确实在IL中使用.tail标记来导致早期丢弃堆栈帧。

尾调用优化可能会使调试变得痛苦，因此例如F#在调试构建中不执行它（但在发布中执行）。项目设置中有一个复选框可在调试中启用。

- AshleyF

---

请注意，JVM语言不支持一般的尾调用优化，但可以支持更受限制的尾递归优化。Scala可以。明确尾递归操作符（如recur）的原因是，如果您期望的尾递归实际上并非如此，那么您会收到一个错误提示，而如果使用隐式尾递归消除，则可能（最终）会收到有关不应发生的堆栈溢出的错误报告。 - Ben

当然可以使用分支而不是调用来进行简单（非相互）递归。但是，当您想要进行调用并消除堆栈帧时，JVM就无法胜任了。 - AshleyF