python - 单个语句中的多个递归

Question

我有一个问题，当下面的代码被执行时，'1'被打印了多少次:

#!/usr/local/bin/python2.7


def rec(n):
    count = 1
    if n > 0:
        count += rec(n - 1) + rec(n - 1)
    print '1'
    return count        

rec(5)

答案 = 63

在尝试解决上面显示的上述问题时，我对递归的某些概念感到困惑。

1> 如何在单个语句中处理多个递归调用的问题。在这个问题中，递归以什么顺序发生，同时发生还是一个接一个发生。

2> 我了解到(在 C 中)递归函数中必须始终有一个条件，它决定了递归的次数，我找不到这样的条件，那么我该如何找出级别数.

Answer 1

让我们逐层看:

rec(5) - you call once, print 1 once
rec(4) - you call twice ONE AFTER ANOTHER (not in parallel). Print 1 twice.
rec(3) - you call 4 times (called twice from the two rec(4)-s), print 1 four times.
rec(2) - call 8 times, print 1 eight times
rec(1) - call 16 times, print 1 sixteen times.
rec(0) - call 32 times, print 1 32 times, but no further recursion called because n==0

32+16+8+4+2+1=63

与递归一样，执行是自下而上执行的，因此您的 rec(0) 将首先打印:

打印的:

rec(0) - 32
rec(1) - 16
rec(2) - 8
rec(3) - 4
rec(4) - 2
rec(5) - 1

如您所见，您可以轻松地将任何 n 的情况概括为级数之和。基本上，这种双重调用递归与简单递归没有什么不同，只是你不调用级别一次，而是调用 2^n 次。