在函数式编程（或其他方式）中递归时，使用显式状态变量的 benefits/limitations 是什么？

Question

我在 Python 玩过函数式编程，发现有两种方法可以用递归代替循环。规范递归技术似乎不需要任何状态，例如下面的 "factorial_canon"。另一种方法是使用状态变量来存储中间结果，例如下面的 "factorial_alter"。

def factorial_canon(value):
    if value == 1:
        return 1
    else:
        return value*factorial_canon(value-1)

def factorial_alter(value, current = 1, state = 1):
    if current <= value:
        return factorial_alter(value, current + 1, state*current)
    else:
        return state

print 'factorial_canon: ', factorial_canon(5)
print 'factorial_alter: ', factorial_alter(5)

结果：

> factorial_canon: 120
> factorial_alter: 120

规范方法适用于小问题，但在实际项目中很快就会变得复杂。替代（基于状态）方法有什么缺点吗？它是否违反了纯函数实现的任何条件，例如，关于可变变量？

我意识到基于状态的方法无法从尾调用优化中获益，但我认为这无关紧要，因为 Python 无论如何都不支持此类优化。

Answer 1

Are there any drawbacks of the alternative (state-based) approach?

好吧，如果你提供函数状态变量，你 interpreter/program 将不得不将它们压入调用堆栈，因此调用所需的时间会更长，调用堆栈也会增长更快（假设没有使用 tail-recursion）。即使使用尾递归，stack frame也会更大，因此需要更多时间（如果是尾递归，你会覆盖stackframe；但覆盖它当然需要时间）。

通常你调用的时候，调用栈是这样的：

+----------------+
| return address |
+----------------+
|        a       |
|        b       |
+----------------+

使用 a 和 b 参数，现在如果你调用 没有尾递归 如果你调用，它将 push，在堆栈上，所以堆栈看起来像：

                          +----------------+
                          | return address'|
                          +----------------+
                          |        a'      |
                          |        b'      |
+----------------+        +----------------+
| return address |  -->   | return address |
+----------------+        +----------------+
|        a       |        |        a       |
|        b       |        |        b       |
+----------------+        +----------------+

现在，如果您使用 tail recrusion，调用堆栈不会被推送，但它的参数会被覆盖：

+----------------+        +----------------+
| return address |  -->   | return address | (no new return address)
+----------------+        +----------------+
|        a       |        |        a'      |
|        b       |        |        b'      |
+----------------+        +----------------+

但是请注意，调用堆栈上的 a 和 b 在进行跳转之前 已修改 。如果你有更多的参数（因为状态参数），这些当然都必须更新，因此需要时间。

Does it violate any conditions of a pure functional implementation, e.g., regarding mutable variables?

不，你在这里不改变任何变量：你通过参数传递一个状态，所以每个变量只设置一次，因为调用中的变量与你收到的变量不同。

I realize that the state-based approach cannot benefit from tail call optimization, but I believe that is irrelevant since Python does not support such optimization anyway.

Python确实不支持尾递归。甚至很难支持这一点，因为 Python 是一种动态编程语言，因此您可以在运行函数导致不同调用的同时更改函数指针。

两个最后的重要说明：

您的 _canon 版本实际上不能使用 tail-recursion 因为需要对结果进行乘法运算，所以调用堆栈必须 unwind 迭代。但是，您的 _alter 版本可以通过某些编程语言用 tail-recursion 实现；和
您的程序计算的不是斐波那契数列，而是阶乘。

Answer 2

不，恰恰相反：state-passing 范式使 TCO 成为可能； simply-recursive "canonical" 版本不是尾递归的，因此 TCO 根本不适用于它。

尾调用优化的本质是栈帧变量（即参数）的重用：

    fact 5:
    fact_state 5 1 1:
    fact_state 5 2 2:
    fact_state 5 3 6:
    fact_state 5 4 24:
    fact_state 5 5 120:
    return 120

简单递归版本必须在递归调用 return 之后执行乘法，因此必须将当前 n 压入堆栈，以乘以 return 值，当递归调用 returns.

尾递归版本在递归调用之前乘以，因此在return之后不需要做任何事情，不需要将任何东西压入堆栈，并且因此只能 return 系统的最终值（只有一个最终值 return ）。

这意味着递归尾调用替换当前调用；它的参数，存储在函数调用框架中，得到重用——就地更新（由编译器改变）；在功能上将整个计算变成一个循环。毕竟，这是 TCO 的目标。

当然在Python中使用递归的方法就是在Python中不使用递归。正如您所说，Python 不提供 TCO。我们的程序仍然运行在其指令集、IOW 循环中具有程序计数器、跳转和可更新寄存器的计算机上。也许当智能尘埃到来时，这会改变。有TCO的递归被转化为循环，这是把TCO放在首位的全部原因。

(see also)

Answer 3

Are there any drawbacks of the alternative (state-based) approach?

不，但是经典递归版本有缺点。想象一下，您正在对奇数数组求和，如果有偶数，结果应该为零。你传给它[1,3,5,6]。在经典意义上你有 1 + 3 + 5 + ? 并且你不知道看到的值。如何让结果为零？

有两种方法。一种是通过累加器，您可以在 factorial_alter 中进行。在基本情况下，您 return 累加器，如果您找到偶数，则停止递归并且 return 为零。

第二种方法是 call-with-current-continuation。您捕获当前延续，这是一个将当前结果作为参数并继续程序其余部分的函数。因此，您可以随时取消并选择总和，在我的示例中 0。 Python 不提供 call/cc.

在函数式编程（或其他方式）中递归时，使用显式状态变量的 benefits/limitations 是什么？

While recursing in functional programming (or otherwise), what are the benefits/limitations of working with an explicit state variable?

python

recursion

state

functional-programming

python-2.7