2

我寻找这个问题的答案，但大多数都是用 Python 以外的编程语言给出的。


现在在这段代码中：

def f(n):
    if n==0:                    
        return 1                
    else:
        m = f(n-1)
        s = n * m
        return s

我知道，如果我使用 n = 3 例如，该函数将使用第二个分支来计算“3-1 = 2”，然后将移动以“2-1 = 1”最终得到 0 然后结果将被返回。

现在在以下情况下会发生什么：

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)


假设我们用 n = 5 执行它。然后将使用第三个分支返回 fib(4) + fib(3)。但那又如何呢？程序将使用哪个数字作为 n、4 或 3 的新值？谢谢你。

4

1 回答 1

9

5作为参数给出的递归级别将调用自身两次，一次是 with 4，一次是 with 3，这两个调用的结果将相加。

同样，调用它4会导致两个调用，一个 with3和一个 with 2。依此类推。所以递归“树”将是：

          _____5_____
         /           \
      __4__           3
     /     \         / \
    3       2       2   1
   / \     / \     / \
  2   1   1   0   1   0
 / \
1   0

您更“经典”的递归（例如阶乘）仅在每个级别调用一次，但这绝不是递归所必需的：

5
 \
  4
   \
    3
     \
      2
       \
        1

如果您想查看发生了什么，请将其更改为以下内容：

def fibonacci(x, n):
    for i in range(x):
        print "  ",
    print "Level %d called with %d"%(x,n)
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(x+1,n-1) + fibonacci(x+1,n-2)

print fibonacci (0,5)

生成的输出：

Level 0 called with 5
   Level 1 called with 4
      Level 2 called with 3
         Level 3 called with 2
            Level 4 called with 1
            Level 4 called with 0
         Level 3 called with 1
      Level 2 called with 2
         Level 3 called with 1
         Level 3 called with 0
   Level 1 called with 3
      Level 2 called with 2
         Level 3 called with 1
         Level 3 called with 0
      Level 2 called with 1
5

您会看到我还删除了某些人使用的完全不必要的 else-after-after-return 范例。它很少需要，并且会降低代码的可读性。

在解释了这一点之后，您还应该让自己意识到递归可能被滥用的情况。尽管斐波那契数列可以优雅地编码为递归解决方案，但它的效率并不过分，因为它在每个子分支中重新计算了许多不同的值（例如fib(2)在给定示例中计算了 3 次，如果调用则更多次）它具有比5) 更大的参数。

甚至阶乘对递归也不是那么好，因为它会非常缓慢地减少“搜索空间”：fact(20)实际上会在堆栈上大约 20 层，而堆栈通常是有限的资源。

最好的递归算法是那些快速减少搜索空间的算法，例如二分搜索，它在每个递归级别上减半。

知道何时使用递归通常与知道如何使用一样重要。

您可以使用阶乘和斐波那契的迭代解决方案，如下所示：

def fact (n): # n = 1..whatever
    result = n
    for i in range (2,n):
        result = result * n

def fib(n): # n = 1..whatever
    me = 1
    if n >1:
        grandparent = 1
        parent = 1;
        for i in range(2, n):
            me = parent + grandparent
            grandparent = parent
            parent = me
    return me

这些都不会冒着耗尽堆栈以获取大量n

于 2013-08-06T03:41:18.030 回答