斐波那契数列的两种递归函数

Question

这是使用递归的斐波那契数列的原始代码

def rec(n):
if n<=1:
    return n
else:
    return ( rec(n-1) + rec(n-2))

n=int(input())

以上代码在第 50 个学期左右变得非常慢。

下面我返回的代码基本上也是一个递归。

n=int(input())
n1,n2,count=0,1,0
def rec(n,n1,n2,count):
    if count<n:
        print(n1)
        nth=n1 + n2
        n1=n2
        n2=nth
        count+=1
        rec(n,n1,n2,count)
rec(n,n1,n2,count)

我的问题是这两种方法都遵循递归（就像真正的递归）吗？

Answer 1

如果一个函数调用自身，它被认为是递归的。

你的两个实现之间的区别是第一个调用自己大约 2**n 次，第二个调用自己大约 n 次。

对于 n = 50，2**50 是 1125899906842624。调用次数太多了！难怪需要很长时间。（例子：想想计算rec(50)时调用rec(10)的次数。很多很多很多次。）

虽然你的两个函数都是递归的，但我会说后者是 "forward iteration"，因为你实际上是在斐波那契数列中向前移动；对于您的第二个 rec(50)，该函数仅递归约 50 次。

一种使递归调用更快的技术称为记忆。参见 "Memoization" on Wikipedia。如果之前已经计算出答案，它会立即返回...因此不是 "re-recursing".

Answer 2

好吧，它们都是递归的，因为你是在其内部调用函数 a()。因此，这两个函数的主要区别在于第一个函数有两个递归调用，第二个函数只有一个。

所以现在，关于另一件事：

Above code gets very slow in around 50th term.

好吧，您可以做一些有趣的事情来更快地完成。看，由于斐波那契数列的递归定义，您要多次进行相同的计算。

例如：假设您要计算 fibonacci(5)，因此您需要计算 fibonacci(4) 和 fibonacci(3)。但是现在，对于 fibonacci(4)，您需要计算 fibonacci(3) 和 fibonacci(2)，依此类推。但是等等，当你完成计算 fibonacci(4) 分支时，你已经计算了 3 和 2 的所有斐波那契，所以当你从第一个递归调用返回到另一个分支 (fibonacci(3)) 时，你已经计算了它.那么，如果有一种方法可以存储这些计算结果以便我可以更快地访问它们呢？你可以用 Decorators to create a memoize class （某种内存来避免重复计算）：

这样我们将把 fibonacci(k) 的每次计算存储在 dict 上，并且我们会在每次调用之前检查它是否存在于字典中，return 如果 True 或者计算它。这种方式更快

class memoize:
    def __init__(self, function):
        self.f = function
        self.memory = {}

    def __call__(self, *args):
        if args in self.memory:
            return self.memory[args]
        else:
            value = self.f(*args)
            self.memory[args] = value
            return value

@memoize
def fib(n):
  if n <= 1:
    return n
  else:
    return fib(n-1) + fib(n-2)

r = fib(50)
print(r)

你可以看到，没有 memoization 花费的时间太长，而使用 memoization 只需要 0.263614.

希望对您有所帮助

Answer 3

这两个函数都是递归的，但是由于最后一个函数将调用自身作为函数中的最后一个动作，它也被描述为尾递归.

尾递归函数可以很容易地转换为循环：

def rec(n, n1=0, n2=1, count=0):
    while count < n:
        print(n1)
        n1, n2, count = n2, n1 + n2, count +1

斐波那契数列的两种递归函数

Recursion function in two types for Fibonacci sequence

python

recursion

fibonacci