带有斐波那契的递归树 -Python-

Question

我正在学习递归，并且写了一个（效率不高的）计算第 n 个斐波那契数的程序：

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

我知道在递归中，可以画出所谓的“递归树”。当我制作这个简单的二进制生成器时：

def binary(length, outstr=""):
    if len(outstr) == length:
        print(outstr)
    else:
        for i in ["0", "1"]:
            binary(length, outstr + i)

我能弄清楚这个树的样子：

但是我搞不清楚斐波那契函数的树会是什么样子！那棵树看起来会怎样呢？

提前谢谢你，

相关文章：

• 暂无相关问题

Answer 1

你可以很简单地用Python中的recursion-visualiser这个包来可视化任何递归函数。你只需要在你的函数上加一个装饰器，其他的它会自动帮你搞定。

二进制字符串

我们先来处理二进制字符串。

from visualiser.visualiser import Visualiser as vs

"""
Problem Link: https://stackoverflow.com/questions/33808653/recursion-tree- 
with-fibonacci-python/60126306#60126306
"""

@vs(node_properties_kwargs={"shape":"record", "color":"#f57542","style":"filled", "fillcolor":"grey"})
def binary(length, outstr=""):
     if len(outstr) == length:
          print(outstr)
     else:
          for i in ["0", "1"]:
               binary(length=length, outstr=outstr + i)

binary(length=3,outstr="")
vs.make_animation("binary_string.gif", delay=2)

下面是输出动画的样子：

最终的树形结构也保存成了：

斐波那契： 现在我们来可视化fib(6)

# Import Visualiser class from module visualiser
from visualiser.visualiser import Visualiser as vs

# Add decorator
@vs(node_properties_kwargs={"shape":"record", "color":"#f57542", "style":"filled", "fillcolor":"grey"})
def fib(n):
    if n <= 1:
        return n
    return fib(n=n - 1) + fib(n=n-2)

def main():
    print(fib(n=6))
    vs.make_animation("fibonacci.gif", delay=2)

if __name__ == "__main__":
    main()

下面是看起来更好的输出：

这是递归树的最终图像：

想看更多例子，可以去这里看看。

Answer 2

比如说，当你调用 fibonacci(4) 的时候，会产生一个递归树。这是因为它需要调用两个函数：fibonacci(3) 和 fibonacci(2)。所以每次调用这个函数时，都会再调用另外两个函数，直到你达到结束的条件。

            4
           / \
          /   \
         /     \
        3       2
       / \     / \
      /   \   /   \
     2     1 1     0
    / \
   /   \
  1     0