从递归到迭代,第二部分:基于时间旅行秘密特性来消除递归 [译]

原文: Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick

这是将递归转化成迭代系列的第二篇。如果你还没有读过上一篇，你应该读一下。它介绍了一些有帮助的术语和背景知识。

上次，如果你还记得的话。我们讨论了将递归函数转化为迭代函数的简单方法。顾名思义，这种方法很简单，而且很机械。唯一潜在的问题是，要使用这种方法，你必须将函数中所有的递归调用转化为尾递归。

这个任务可能很棘手。因此，我们还讨论了将递归调用转化为尾递归的秘密函数技巧。这个技巧适用于简单的递归调用，但当调用不那么简单的时候，就需要一个更强大的版本。

这就是这篇文章的主题：时空旅行的秘密。这就像将T-800送到过去(来自电影终结者)，终止一个函数的递归性

是的

但是我们得慢慢来。所以，坚持使用早起的例子，为后面困难例子做好准备。

说够了！让我们从一个实际的例子开始。

如果你想要另外一个例子，这里还有一个斐波那契数列的逐步转化

计算二项式系数

整数n和k的二项式系数给出了从一组n个项目中选择k个项的方法。因此，它通常发音为”n choose k”。它在组合学和统计学中很常见。也经常出现在算法分析中。事实上，在Granham, Knuth和P atashnik的Concrete Mathematics有一整章是在介绍它。

定义如下:

但是这种形式会给电脑带来各种各样的问题。幸运的是，具体数学一书帮助我们指出了一个拯救生命的吸收等式：

这是一个正在等待发生的递归函数

在这个等式中，

def binomial(n, k):
  if k == 0:
    return 1
  return n * binomial(n-1, k-1) // k

在进一步讨论之前，有一点需要注意。数学和计算机数学是不同的。在数学中，但是在计算机数学中，方程不一定成立，因为计算精度是有限的。或者，在我们的例子中，因为我们处理的是整数除法，他会丢弃余数(顺便说一下，在Python中， // 是去除余数的除法运算符)。出于这个原因，我一直小心的使用公式

1	n * binomial(n-1, k-1) // k

而不是使用直译形式

1	(n // k) * binomial(n-1, k-1)

如果你试一试，你会发现通常会得到错误答案。好了，挑战摆在我们面前，准备好反递归二项式了吗?

再一次，秘密特征技巧

但是，首先我们必须将函数的递归调用转化成尾递归形式。你还记得怎么做，对吧？当然是使用秘密特征技巧了！作为上一次的复习，这里有一个简单的技巧:

找到一个不是尾部调用的递归调用
确定在该调用和return语句之间正在进行哪些工作
使用一个秘密功能扩展函数来执行该工作，该工作由一个新的累加控制器参数控制，该参数有一个默认值，该参数会导致该函数不执行任何操作
使用秘密功能来消除旧工作
你现在有尾部调用了
重复操作，知道所有的递归调用都是尾部调用

让我们按照数字来过一遍

找到一个不是尾部调用的递归调用

在这里只有三行逻辑，我们不是在谈论火箭科学

def binomial(n, k):
  if k == 0:
    return 1
  return n * binomial(n -1, k-1) // k

确定在该调用和return语句之间正在进行哪些工作

在我们看来，将递归调用从return语句中移除，并将其替换为变量x

1 2	x = binomial(n-1, k-1) return n * x // k

现在我们可以把额外的工作看作是x上单独操作的函数: 在左边乘以一个数，在右边除以另外一个数：

1 2	def work(x, lmul, rdiv): return lmul * x // rdiv

对于这么简单的函数，你可以将它保存在头脑中，并根据需要将它们内联到代码中。但是对于更加复杂的函数来说，像这样将它们分开却是很有帮助。在这个例子中，我假设功能函数更加复杂，只是为了演示一下怎么做。

用一个秘密特性扩展函数来完成这项工作，由一个新的累加器参数控制 – 在本例中是一个pair(lmul, rdiv) – 使用一个默认值，该值导致它不做任何事情

def work(x, lmul, rdiv):
  return lmul * x // rdiv

def binomial(n, k, lmul=1, rdiv=1):
  if k == 0:
    return work(1, lmul, rdiv)
  return work(n* binomial(n -1, k-1) // k, lmul, rdiv)

注意，我只是机械的将所有return {whatever}语句转化为return work({whatever}, lmul, rdiv)

使用秘密功能来消除旧工作

看看最后一行会发生什么

def work(x, lmul, rdiv):
  return lmul * x // rdiv

def binomial(n, k, lmul=1, rdiv=1):
  if k == 0:
    return work(1, lmul, rdiv)
  return binomial(n-1, k-1, lmul*n, k*rdiv)

现在你就得到了一个尾调用！

的确，我们做到了！剩下的就是内联唯一剩下的工作调用:

def binomial(n, k, lmul=1, rdiv=1):
  if k == 0:
    return lmul * 1 // rdiv
 	return binomial(n-1, k-1, lmul*n, k*rdiv)

为了简化return语句中不必要的乘1操作：

def binomial(n, k, lmul=1, rdiv=1):
  if k == 0:
    return lmul // rdiv
  return binomial(n-1, k-1, lmul*n, k*rdiv)

重复直到所有的递归调用都是尾调用

这里只有一个，所以搞完了

通过将所有递归调用(只有一个)转化成尾部调用，我们可以通过简单方法轻松地将函数转化为迭代形式。下面是将函数体加载到一次性循环并将尾部调用转化为复制-continue之后得到的结果

def binomial_iter(n, k, lmul=1, rdiv=1):
  while True:
    if k == 0:
      return lmul // rdiv
    (n,k,lmul,rdiv) = (n-1, k-1, lmul*n, k*rdiv)
    continue
    break

最后，我们可以整理一下，在这个过程中把累加器塞进函数体中让它完全保密：

def binomial_iter(n, k):
  lmul = rdiv = 1
  while k>0:
    (n, k, lmul, rdiv) = (n-1, k-1, lmul*n, k*rdiv)
  return lmul // rdiv

现在我们有了一个原始二项式函数的迭代版本！

一个简短的警示

接下来这个部分很微妙，但是很重要。要理解发生了什么，你首先需要看到它。所以，再一次，让我们使用Online Python Tutorial的优秀的Python运行时可视化。如果可以，请在新标签页中打开下面的链接，然后继续阅读

可视化执行二项式(39, 9)

点击前进按钮来推进每一步的计算。当你到了第22步，递归版本已经完全加载了嵌套的栈帧，慢慢点击。当你前进时，观察返回值(红色)。看到它时如何轻轻地攀升到最后的答案211915132，从未超过这个值吗？

现在继续步入迭代版本。随着你的前进，观察lmul的数值。看看它是如何快速增长的，最后达到了惊人的76899763100160？

这个区别很重要，虽然这两个版本都计算出了正确的答案，但是最初的递归版本可以在不超过32位有符号整数的范围的情况下计算出正确的结果。

Python的整数，对于我们来说是幸运的，可以根据需要增长来保持它们的值，所以在这种情况下，我们不必担心溢出，但并不是所有我们可能想要使用递归到迭代技术的语言都提供这样的保护。这是你下次在C语言中把递归转成迭代需要注意的东西。

typedf int32_t Int;

Int binomial(Int n,Int k){
  if (k == 0)
    return 1;
  return n*binomial(n-1, k-1)/k;
}

Int binomial_iter(Int n,Int k){
  Int lmul=1, rdiv =1;
  while (k>0){
    lmul *= n; rdiv *= k; n -=1; k -= 1;
  }
  return lmul/rdiv;
}

int main(int argc, char* argv[]){
  printf("binomial(39,9)       = %ld\n", (long)binomial(39, 9));
  printf("binomial_iter(39,9)  = %ld\n", (long)binomial_iter(39, 9));
}

/* Output with Int = int32_t:
binomial(39, 9) 		 = 211915132
binomial_iter(39, 9) = -4481      <-- oops!
*/

在任何情况下，更大的整数都会比较慢，消耗更多的内存。在一个重要的方面，原始的、递归算法更好。我们失去了一些重要的东西。

现在我们回到重点

结合律和交换律的重要性

事实证明，我们的二项式迭代版本是原始版本的邪恶双胞胎。它的堆栈用法看起来很迷人，但它的其他地方却不对劲。有些东西我们很难说清。有什么不同呢？

归根结底，这一切都取决于分组和排序决策。我们在代码转换期间忽略的隐式分组和排序决策。

考虑两个版本的计算方式

首先，递归版本。我们从n=5, k=2开始，然后递归的展开表达式

直到k=0，这一系列的展开是这样进行的

在每一步(除了基础情况)，我们都先执行n的乘法运算，然后再进行k的除法运算。正是k的除法避免了中间结果的失控。

现在让我们看看迭代版本。发生了什么并不是那么明显。但我们可以搞清楚。我们从1的两个累加器开始，然后循环k的递减值，构建累加器，直到k=0，此时我们返回累加器的商

所以计算式为:

分子和分母都在疯狂增长，知道最后做除法，这不是一个好的趋势

那么，为什么在我们之前的文章中，秘密特征技巧对factorial非常有效，但现在却让我们失望了? 答案是，在factorial中，每个递归调用与其return语句之间所做的额外工作是乘法，仅此而已。而乘法(不溢出)是符合交换和结合律的。意思是，排序和分组并不重要。

那么，这个教训就是。在使用秘密特征技巧之前，要仔细考虑排序和分组是否重要。如果它很重要，你有两个选择。一：你可以修改你的算法，让排序和分组不重要，然后再使用秘密特征技巧(但这个选项通常是很难解决的)。二：你可以使用时间旅行秘密特征技巧，它可以保留排序和分组。而这个技巧就是我们一直在等待的。

是时候了～～～

时空穿越秘密功能技巧

接下来即将发生的事情是如此令人匪夷所思，以至于你也许应该买杯酒来准备一下。这就像是将《终结者》中的T-800和《盗梦空间》中的梦中梦分层结合在一起，当围绕着归纳证明的量子场坍塌时，现实发生了瞬间的逆转

是的，这超酷

准备好你的饮料，我们来搞这个

让我们回到最初的递归的二项式函数

def binomial(n, k):
  if k == 0:
    return 1
  return n*binomial(n-1, k-1)//k

我们的目标是创建一个等价的迭代版本，完全保留原始版本的特性。那么，我们到底要怎么做呢？

先别想这个

让我们停下来思考一下递归函数在做什么。我们调用它来计算的答案，但这个答案取决于之前的的答案，所以它调用自己来获得这个答案。等等… 直到最后，它找到一个基础的已知的的答案。然后从基础问题建立每个后续的答案.

所以，事实上，的答案只是需要更早答案的整个时间轴上的最后一个元素

那又怎样? 我们为什么要关心?

因为我们已经看了《终结者》几百遍了！当我们看到时间线的时候，我们知道如何在现在解决一个问题。我们派一个终结者到过去去重写时间线，这样问题就不会在一开始产生了。

我们的二项式递归问题呢？我们已经看过它的时间线了。

没错，它就要成为现实了。

还有一件事。这些步骤中的每一个都保留了原始函数的行为。你可以在每一步之后运行你的单元测试，它们应该都能通过。

让我们开始吧。

将T-800终结者单元送入函数的时间线，回到

😯，我们没有T-800终结者单元？没问题，假设我们已经将T-800终结者单元送入函数的时间线，回到

这很容易，接下来是什么?

将递归调用和周围的工作移动到一个帮助函数中

这样做看起来没什么必要，但是可以防止错误。你会犯错吗？那就干脆把助手函数写出来吧。我把它称作step，你很快就会明白为什么了

def step(n, k):
  return n*binomial(n-1, k-1) // k

def binomial(n, k):
  if k == 0:
    return 1
  return step(n, k)

将帮助函数划分为3个基础部分

它们是：

递归调用得到前一个的答案
从计算的答案
只应用于的return语句

def step(n, k):
  previous_x = binomial(n-1, k-1)
  x = n*previous // k
  return x

def binomial(n, k):
  if k == 0:
    return 1
  return step(n, k)

秘密准备接收T-800终结者单元的通信

你看，一旦T-800把它的手伸向时间线的早期，我们就可以利用它的知识来消除递归，我们只需要想办法把这些知识从T-800身上传到我们身上，它被困在了过去

幸运的是，我们看过时间旅行的电影，所以我们知道这个问题是如何解决的。我们就用一个死胡同(dead drop, 间谍之间利用秘密地点传递物品或者信息，不需要直接见面)！那是一个预先安排好的地点，T-800会在那里放下过去的值，我们会在未来检查它们。

所以，对照之前对T-800的安排，我们将用一个秘密的功能来扩展我们的助手的功能，检查死胡同的前一个值，如果有的话，使用它来中断递归调用链

def step(n, k, previous_x=None):
  if previous_x is None:
    previous_x = binomial(n-1, k-1)
  x = n * previous_x // k
  return x

def binomial(n, k):
  if k == 0:
    return 1
  return step(n, k)

通常，我们将helper看作是用和来计算的一个函数，因为参数可以被安全的忽略。除非T-800将一个值放入其中，否则它不起作用。

但是，如果T-800确实写入了一个值，我们可以把这个函数看作如下变换:

注意，进去，出来。从这个小例子中我们可以做一些非常疯狂的事情。比如：将时间倒流。也就是说，通过递归时间线向前计算，而不是向后计算

Yeah

继续读下去

修改helper的return语句，使其非秘密参数也能通过

def step(n, k, previous_x = None):
  if previous_x is None:
    previous_x = binomial(n-1, k-1)
  x = n*previous_x // k
  return (n, k, x)

def binomial(n,k):
  if k == 0:
    return 1
  return step(n, k)[2]

现在，我们的helper表示如下变换：

非常有趣

应用与helper的return语句中的非秘密参数，与递归调用中应用与它们的转换相反。

由于我们在递归调用中传递了n-1, k-1，所以我们通过return语句将n+1, k+1传递出去

def step(n,k,previous_x=None):
  if previous_x is None:
    previous_x = binomial(n-1, k-1)   # <--- 看这里
  x = n*previous_x // k
  return (n+1, k+1, x)    #  <--- 这里

def binomial(n, k):
  if k == 0:
    return 1
  return step(n, k)[2]

现在，我们的helper表示如下变换:

现在，我们可以逆转时间的流向

当我们开始使用我们最初的递归函数的时候，如果我们要求它提供, 函数必须得到, 然后得到，以此类推，直到达到。看到这种工作方式，真让人心疼.

但是现在，我们可以采取另外一种方式。如果我们有，我们可以得到，直接求值，不需要递归。输入得到 . 继续～～

为什么，如果我们知道n1, k1和x0，我们可以不使用递归计算出整个系列的值

那么，让我们来看看这些数值吧！

确定时间线开始时的初始条件

对于这个简单的例子，大多数人可能可以通过检查来确定初始条件。但我还是要写一下这个过程，你永远不知道什么时候你会需要它。因此，

时间线的起点时什么？就是当递归二项式函数多次调用自己，最后达到它的一个基本情况时，它定义了时间轴中的第一个条目，将时间轴固定在时间i=0。这个例子中基本情况很容易找到，因为我们已经分解了步骤逻辑；二项式剩下的就是基本情况逻辑了。很容易看出来，只有一种基本情况，即k=0

def step(n, k, previous_x=None):
  if previous_x is None:
    previous_x = binomial(n-1, k-1)
  x = n * previous_x // k
  return (n+1, k+1, x)

def binomial(n, k):
  if k == 0:   #  <--- 基本情况
    return 1
  return step(n, k)[2]

从这个basic case我们可以知道，在时间线的最开始，我们一定有i=0, k=0 和 x =1。因此，我们知道和。因为时间线结束于，我们知道

让我们把目前我们所知道的时间线直观的表现出来

time :	0	1	2	…	t
:	-	-	-	…	n
:	0	-	-	…	k
:	1	-	-	…	?

我们最终要的是的答案，在时间轴上打上问号

现在要确定和, 要做到这一点，我们必须回答这个问题，我们如何从得到？

我们已经知道答案了！step帮助函数计算. 所以看它的逻辑，它是如何改变n和k的值的

因此，

由于的i 从开始，并且每一步加1，我们得到

当i=t的时候，我们从上面的方程知道

最后，我们可以计算出n1

现在我们有了初始条件:

所以现在我们对时间线的了解是这样的

time :	0	1	2	…
:			-	…	n
:	0	1	-	…	k
:	1	-	-	…	?

有了这些知识，我们就可以通过时间线，从时间开始向前推进，从到，以此类推，直到最后一步，当的时候我们得到了答案

来吧

在主函数中，迭代step帮助函数t次，从初始条件开始，然后返回

def step(n, k, previous_x=None):
  if previous_x is None:
    previous_x = binomial(n-1, k-1)
  x = n*previous_x // k
  return (n+1, k+1, x)

def binomial(n, k):
  if k == 0:
    return 1
  t = k
  (n,k,previous_x) = (n-k+1, 1, 1)
  for _i in range(1, t+1):
    (n,k,previous_x) = step(n,k,previous_x)
  return previous_x

牛逼！这100%是迭代，但还能更牛逼🐂！

去掉原函数的基例

由于我们的迭代是从基例开始的，所以基例已经被纳入我们新的迭代逻辑中

def step(n, k, previous_x=None):
  if previous_x is None:
    previous_x = binomial(n-1, k-1)
  x = n*previous_x // k
  return (n+1, k+1, x)

def binomial(n, k):
  t = k
  (n,k,previous_x) = (n-k+1, 1, 1)
  for _i in range(1, t+1):
    (n,k,previous_x) = step(n,k,previous_x)
  return previous_x

去掉step函数的秘密功能

由于previous_x现在总是得到一个值，我们可以将它作为函数的一个必要部分。

def step(n,k,previous_x):  # <- 删除默认值和base case
  x = n*previous_x // k
  return (n+1,k+1,x)
  
def binomial(n,k):
  t = k
  (n,k,previous_x) = (n-k+1, 1, 1)
  for _i in range(1, t+1):
    (n, k, previous_x) = step(n, k, previous_x)
  return previous_x

将step内联

def binomial(n, k):
  t = k
  (n,k,previous_x) = (n-k+1, 1, 1)
  for _i in range(1, t+1):
    x = n*previous_x // k
    (n,k,previous_x) = (n+1,k+1,x)
  return previous_x

修饰一下

这个例子已经很完美了，但是我们可以把变量x替换掉

而且，因为, 我们可以将for循环的变量_i 替换为并去掉的递增逻辑。

而且，当我们想更近一步优化的时候，有一个明显的优化。二项式系数的一个性质是。我们代码的一个性质是它运行t=k步。所以当k>n-k时，我们可以通过求解来减少步骤。让我们在开头添加几行来实现这种优化

当然，写一下docstring, 做一个好人吧~~

最终结果
1
2
3
4
5
6
7
8
9
def binomial(n, k):
if k > n-k:
k = n-k

t = k
(n, previous_x) = (n-k+1, 1)
for k in range(1, t+1):
(n, previous_x) = (n+1, n*previous_x // k)
return previous_x

让我们回顾一下刚才的工作，这是心灵的震撼：

我们将一个想象中的T-800终结者单元送回函数的时间线中
然后我们在我们的功能中增加了一个秘密功能，允许T-800向我们发送时间线过去的数值
然后，我们用这些值打破递归链，逆向流转时间，向前和迭代计算时间线，而不是向后和递归
在函数完全迭代的情况下，我们删除了秘密功能，想象中的T-800眨眼间就消失了。(在命运的讽刺中，T-800通过秘密功能dead drop，准确的将我们需要的东东传递到我们手中，将它们从历史中抹除)
现在，我们有了一个快速、高效、保护属性的递归函数迭代版本，而且它和我们希望从头开始的任何东西一样好(请看它的实际操作 – 只需要一个栈帧，而且很简单)
而且，最重要的是，我们是采用机械的，可重复的流程来完成的。

从递归到迭代,第二部分:基于时间旅行秘密特性来消除递归 [译]

计算二项式系数

再一次，秘密特征技巧

一个简短的警示

结合律和交换律的重要性

时空穿越秘密功能技巧

ficapy

博客起航

IDM-Internet Download Manager

everything--文件搜索神器

everything进阶教程

Snagit-截图兼图片转换软件

xnview-图片查看

DeskPins-窗口置顶

傲梅分区助手--傻瓜化分区软件

excel数字递增批量打印

pip使用国内镜像