如何定位递归条件？

Question

我的代码如下。

我首先尝试了为每种情况编写代码，因此给定n= 4，我的代码如下所示：

a = overlay_frac(0,blank_bb,scale(1/4,rune))
b = overlay_frac(1/4,blank_bb,scale(1/2,rune))
c = overlay_frac(1/2,blank_bb,scale(3/4,rune))
d = overlay_frac(3/4,blank_bb,scale(1,rune))
show (overlay(a,(overlay(b,(overlay(c,d))))))

我的理解是递归模式是：

a = overlay_frac((1/n)-(1/n),blank_bb,scale(1/n,rune))
b = overlay_frac((2/n)-(1/n),blank_bb,scale(2/n,rune))
c = overlay_frac((3/n)-(1/n),blank_bb,scale(3/n,rune))
d = overlay_frac((4/n)-(1/n),blank_bb,sale(4/n,rune))

因此，我提出的递归模式是：

def tree(n,rune):
    if n==1:
        return rune
    else:
        for i in range(n+1):
            return overlay(overlay_frac(1-(1/n),blank_bb,scale(i/n,rune)),tree(n-1,rune))

当我对此进行硬编码时，一切都很好，但我怀疑我没有正确地进行递归。我哪里错了？

Answer 1

实际上，您正在尝试在递归调用中进行迭代。你可以使用一个内部函数来记忆你的状态，而不是使用循环。您定义的系数实际上随n和i一起更改，但对于给定的n，它仅随i更改。你需要用内部函数记住的状态就是i，这和你在i中循环一样。

你仍然可以通过这样做来实现你的目标

def f(i, n): 
  return overlay_frac((i/n)-(1/n),blank_bb,scale(i/n,rune))

# for each iteration, you check if i is equal to n
# if yes, return the result (base case)
# otherwise, you apply next coefficient to the previous result
# you start with i = 0 and increase by one every iteration until i reach to n (base case)
# notice how similar this recursive call looks like a loop
# the only difference is the status are updated within the function call itself
# therefore you will not have the problem of earlier return 
def recursion(n):
  def iteration(i, out):
    if i == n:
      return out
    else:
      return iteration(i+1, overlay(f(n-1, n), out))
  return iteration(0, f(n, n))

这里，假设n是您想要应用的覆盖次数。当为n = 0时，最后一个系数f(n, n)上不应用任何函数。当为n = 1时，输出将使用i = n - 1对系数应用一次，对i = n对系数应用一次。

这种方式避免了循环中较早的返回。

实际上，您可以通过向外部函数添加额外的参数来省略内部函数。然后，您需要分配默认的初始i。内部函数在这里实际上并不是必需的。关键是使用函数参数来存储状态(在本例中为变量i )。

def f(i, n): 
  return overlay_frac((i/n)-(1/n),blank_bb,scale(i/n,rune))

def recursion(n, i=0):
    if i == n:
      return f(n, n)
    else:
      return overlay(f(n-1, n), recursion(n, i+1))

Answer 2

您的前两个代码块不对应于相同的操作。这将等同于您的第一个块(在Python 3中)。

def overlayer(n, rune):
    def layer(k):
        # Scale decreases linearly with k
        return overlay_frac((1 - (k+1)/n), blank_bb, scale(1-k/n, rune))
    result = layer(0)
    for i in range(1, n):
        # Overlay on top of previous layers
        result = overlay(layer(i), result)
    return result

show(overlayer(4, rune))

Answer 3

让我们再看看你的方程式：

a = overlay_frac(0,blank_bb,scale(1/4,rune))
b = overlay_frac(1/4,blank_bb,scale(1/2,rune))
c = overlay_frac(1/2,blank_bb,scale(3/4,rune))
d = overlay_frac(3/4,blank_bb,scale(1,rune))
show (overlay(a,(overlay(b,(overlay(c,d))))))

你写的“递归”不是递归公式。如果你将你的递归公式与你给我们的公式进行比较，你可以推断出n=4，这是没有意义的。对于递归模式，您需要将内部变量描述为具有不同参数的相同表达式的表现形式。也就是说，您应该替换：

f_n = overlay_frac((1/4)*(n-1),blank_bb,sale(n/4,rune))

这样f_1=a, f_2=b等。

然后，您要计算的递归公式将转换为：

show (overlay(f_1,(overlay(f_2,(overlay(f_3,f_4))))))

您可以在代码中将函数f_n编写为f(n) (也可能是其他参数)，然后执行

def recurse(n):
    if n == 4:
        return f(4)
    else:
        return overlay(f(n),recurse(n+1))

然后调用：

show( recurse (1))

您需要断言n<5和integer，否则将陷入无限循环。可能仍然会有一些错误，但应该是这样的。然而，一旦你真正像这样写好了它，它(也许)就不再有什么意义了。如果你只想为n_max=4做这件事，那就是。只需用f_1,f_2,f_3,f_4替换a,b,c,d，即可在一行中调用该函数