python - 双重递归背后的概念

Question

谁能解释一下这种双重递归是如何工作的？我需要理解 Action 的顺序(即这个算法是如何工作的)我知道普通(单一)递归是如何工作的。例如，像这样:

Q=lambda n:n>3 and Q(n-3)or n
print(Q(10))

因此，当 n>3(在我们的例子中为 True)时，我们转移到递归并减去 3，然后我们得到 7 -> 它大于 3，所以我们重复我们的操作(因为它仍然是 True)并且现在我们有 4，它仍然大于 3，所以我们再次重复它，现在我们有 1。1 小于 3，现在它为 False。在 False 或 n -> 中，我们得到 n，所以这个单一递归的结果将是 1 (n=1)。这对我来说是绝对清楚的。

但是我完全陷入了双重递归的困境。我正在尝试打印，但到目前为止我不知道这里发生了什么。请帮忙。指向此函数的操作顺序。

F=lambda n:n>3 and F(n-3)+F(n-2)or n
print(F(10))

Answer 1

您始终可以将递归堆栈视为一棵树。如果你有双重递归，那么考虑你有一个二叉树，即递归堆栈中的每个节点都有两个分支。

如果您有单递归，则将其视为倾斜树，如果您有三重递归，则将其视为三元树，等等。对于 n 递归，考虑一个 n-ary 树。

例子:

F=lambda n:n>3 和 F(n-3)+F(n-2)

令 n = 10;

          10
        /   \
       7      8
      / \    / \
     4  5    5  6
    / \ /\  / \ /\
   1  2 2 3 2 3 3 4 -----> returns here except last right node (i.e. 4)
                  /\
                 1  2 -----> returns here because its the base case (as n < 3)

所以，输出是 1+2+2+3+2+3+3+1+2 即 19

此外，您始终可以打印出函数调用以更正确地理解递归。

例如，我在打印函数调用堆栈时未使用 lambda 编写了相同的程序。

程序

F = lambda n:n>3 and F(n-3)+F(n-2) or n

def indent(n):
    for i in xrange(n):
        print '    '*i,

# the second argument is just passed to print the apt space before the print statement
def fun(n, rec_cnt):
    indent(rec_cnt)
    print 'fun(' + str(n) + ')'
    if n <= 3:
        return n
    else:
        return fun(n-3, rec_cnt+1) + fun(n-2, rec_cnt+1)


# print F(10)

print fun(10, 0)

你可以看到下面的输出:

fun(10)
 fun(7)
      fun(4)
               fun(1)
               fun(2)
      fun(5)
               fun(2)
               fun(3)
 fun(8)
      fun(5)
               fun(2)
               fun(3)
      fun(6)
               fun(3)
               fun(4)
                            fun(1)
                            fun(2)
19