algorithm - 了解递归代码的行为

Question

我正在复习几周后要回答的一个考试的旧试题，下面的问题让我陷入了困境：
一个有限的位序列被表示为一个列表，其中的值来自集合{0,1}-例如，[0,1,0]，[1,0,1,1]。
[]表示空列表，[b]是由一位b组成的列表。对于非空列表l，head（l）返回l的第一个元素，tail（l）返回从l中删除第一个元素获得的列表。
A:L表示在列表L的开头添加A形成的新列表。
例如：
•头部（[0,1,0]）=0，尾部（[0,1,0]）=[1,0]，
•头（[1]）=1，尾（[1]）=[]，和
•1:[0,1,0]=[1,0,1,0]。
考虑以下功能：
•f1将一个列表作为输入并返回另一个列表。

f1(s):
 if (s == []) then return([1])
  else if (head(s) == 0) then return(1:tail(s))
  else if (head(s) == 1) then return(0:f1(tail(s)))
 endif

•f2接受一个位和一个列表作为输入并返回一个位。

f2(b,s):
 if (s == []) then return(b)
  else if (head(s) == 0) then return(f2(not(b),tail(s)))
  else if (head(s) == 1) then return(not(b))
 endif

•g1接受一个非负数作为输入并返回一个列表。

g1(n):
 if (n == 0) then return([0])
  else return f1(g1(n-1))
 endif

•G2接受一个非负数作为输入，并返回一个位。

g2(n):
 if (n == 0) then return(0)
  else return f2(g2(n-1),g1(n))
 endif

g2（7）和g2（8）的值是多少？
g2（256）和g2（257）的值是多少？
到目前为止，我只能理解f1的行为（如果head为0并返回，则将head替换为1）否则，将head替换为0，并在列表的其余部分调用自己。）和g1（n），这与f1应用于[0]n次（f1（f1（…f1（[0]））-n次）相同。
有什么结构化的方法可以解决这类问题吗？（尤其是在时间压力下。）
编辑：在列表s的第一个1之前，f2将位b反转0的次数。
g2（）仍然是个谜。

Answer 1

纸笔评估
最好的方法就是开始。获取前面函数的定义并开始纸笔评估。这个问题要求我们比较g2(7)和g2(8)，但是观察g2我们发现我们需要理解f2和g1，所以让我们从这里开始。因为g1的值是首先计算的，所以我们将首先熟悉g1
我只想把一些价值观推进去，然后得到结果。我将从0开始，因为在查看g1之后，这似乎是最容易计算的

g1(0) => [0]

g1(1) => f1(g1(0)) => ... stop, do not recompute `g1(0)` here, we already know the answer above
      => f1([0])
      => [1]

g1(2) => f1(g1(1)) => we already know `g1(1)` from above
      => f1([1])
      => 0 : f1([])
      => [0,1]

g1(3) => f1(g1(2)) => we already know `g1(2)`
      => f1([0,1])
      => [1,1]

g1(4) => f1(g1(3)) => reuse `g1(3)`
      => f1([1,1])
      => 0 : f([1]) => we already know `f1([1])`
      => 0 : [0,1]
      => [0,0,1]

我已经看到了一个模式。你…吗？ g1正在为 little endian bit order中的 n生成1和0的二进制序列

g1(0) => [0]
g1(1) => [1]
g1(2) => [0,1]
g1(3) => [1,1]
g1(4) => [0,0,1]
g1(7) => ?
g1(8) => ?

我猜分别是 [1,1,1]和 [0,0,0,1]我们继续看看是否正确。。。

g1(5) => f1(g1(4))
      => f1([0,0,1])
      => [1,0,1]

g1(6) => f1(g1(5))
      => f1([1,0,1])
      => [0,1,1]

g1(7) => f1(g1(6))
      => f1([0,1,1])
      => [1,1,1]

g1(8) => f1(g1(7))
      => f1([1,1,1])
      => 0 : f([1,1]) => we already know f1([1,1])
      => 0 : [0,0,1]
      => [0,0,0,1]

取得良好进展
嘿，我们的猜测是对的评估g（0）到g（8）需要30-45秒——大约5.5分钟，我们非常清楚 g1和 f1是如何工作的。我们对 g1的理解稍微好一点，因为我们知道它只需要一个数字，然后吐出二进制位序列来表示输入的数字。 f1在它的工作方式上有点神奇，但最酷的是它并不重要——这个问题要求我们比较 g2的值，因此只要我们能够计算 g2的值，那么我们是否对其他函数有很好的理解并不重要。
上次评估 g1给了我们一些关于 f1的有价值的见解，看起来与 g2相关的 f2的情况是一样的。现在我们有了一些可以引用的 g1值，让我们尝试计算一些 g2值–我将像上次一样从 0开始

g2(0) => 0

g2(1) => f2(g2(0),g1(1)) => we already know `g2(0)` and `g1(1)`
      => f2(0, [1])
      => 1

g2(2) => f2(g2(1), g1(2)) => we already know these!
      => f2(1, [0,1])
      => f2(0, [1])
      => 1

g2(3) => f2(g2(2), g1(3))
      => f2(1, [1,1])
      => 0

g2(4) => f2(g2(3), g1(4))
      => f2(0, [0,0,1])
      => f2(1, [0,1])
      => f2(0, [1])
      => 1

在这一点上，我还没有看到太多的模式。起初我想 g2可能会告诉我们给定的整数是偶数还是奇数，但事实并非如此我在想的另外一件事是，对于2的幂，它返回 1，对于2的非幂，它返回 0。这是一个奇怪的函数。让我们继续找出

g2(5) => f2(g2(4), g1(5))
      => f2(1, [1,0,1])
      => 0

g2(6) => f2(g2(5), g1(6))
      => f2(0, [0,1,1])
      => f2(1, [1,1])
      => 0

g2(7) => f2(g2(6), g1(7))
      => f2(0, [1,1,1])
      => 1

g2(8) => f2(g2(7), g1(8))
      => f2(1, [0,0,0,1])
      => f2(0, [0,0,1])
      => f2(1, [0,1])
      => f2(0, [1])
      => 1

一种意想不到的模式出现了
好的，我们已经到达 g2(7) == 1和 g2(8) == 1。我们的2次方理论肯定没有成功，但我们可以看到另一个模式已经出现- g2如果位序列包含奇数个 1s，则返回 1，如果位序列包含偶数个 0s，则返回 1。
我在这里做了一个小事实表来检验我的猜测

g1(0) => [0]          ones(0) => 0    odd?(ones(0)) => 0    g2(0) => 0
g1(1) => [1]          ones(1) => 1    odd?(ones(1)) => 1    g2(1) => 1
g1(2) => [0,1]        ones(2) => 1    odd?(ones(2)) => 1    g2(2) => 1
g1(3) => [1,1]        ones(3) => 2    odd?(ones(3)) => 0    g2(3) => 0
g1(4) => [0,0,1]      ones(4) => 1    odd?(ones(4)) => 1    g2(4) => 1
g1(5) => [1,0,1]      ones(5) => 2    odd?(ones(5)) => 0    g2(5) => 0
g1(6) => [0,1,1]      ones(6) => 2    odd?(ones(6)) => 0    g2(6) => 0
g1(7) => [1,1,1]      ones(7) => 3    odd?(ones(7)) => 1    g2(7) => 1
g1(8) => [0,0,0,1]    ones(8) => 1    odd?(ones(8)) => 1    g2(8) => 1

所以 g2(x)等于 odd?ones(x)，至少在 0 <= x <= 8的地方。评估 g2(0)到 g2(8)大约需要10分钟，分析模式可能需要5-10分钟，总共大约25分钟。但现在我们知道了在不进行所有繁琐的逐步递归的情况下计算 g(256)和 g(257)所需的一切
密码被破解了
将256转换成二进制，我们知道 g1(256)是 [0,0,0,0,0,0,0,0,1]，同样 g1(257)是 [1,0,0,0,0,0,0,0,1]，所以现在很容易计算 g2(256)并将其与 g(257)进行比较

g1(256) => [0,0,0,0,0,0,0,0,1]    ones(256) => 1    odd?(ones(256)) => 1    g2(256) => 1
g1(257) => [1,0,0,0,0,0,0,0,1]    ones(257) => 2    odd?(ones(257)) => 0    g2(257) => 0

就这些

g2(7) => 1
g2(8) => 1
g2(256) => 1
g2(257) => 0

再加上几分钟，我们应该在30分钟左右-根据熟练程度和识别模式的能力，给或拿50%。
选择一个图案，任何图案
哦，嗯，也许你找到了一个不同的模式-那完全可以！重要的是你要尽你最大的能力去检验它（记住你的时间限制）。
f2将位 b反转为列表中第一个1之前的0的次数。
我看到你对 s有一些理解，但这有点问题，因为 f2最初等于 b假设我们要计算 g2(n - 1)其中 f2(b, s)是 b。我们被困是因为我们还不知道那是什么不幸的是，这是对 g2(1234)
这就是为什么我能够（或者幸运地）在 f2和 g1之间建立一个已知输入之间的相关性，这与 g2或 f1完全无关。一旦我能看到 f2和 g1是如何工作的，我甚至不需要计算 g2或 f1来评估 f2和 g(256)。这是一个巨大的收获，因为我有效地从纸笔评估模型中删除了 g(257)和 f1，并且仍然得到了 f2和 g1的正确答案。如果没有达到这一点，我将被困在寻找另一个相关性或手动评估一直到 g2。这对考试来说太长时间了。