利用graphviz模块展示斐波那契数列的递归函数调用图（Python）

  在博客动态规划法（一）从斐波那契数列谈起中，在求解斐波那契数列的第n项时，我们采用了递归方法和动态规划法来求解，当然递归方法的效率很差。本文将利用graphviz模块来展示斐波那契数列的递归函数调用图。
  利用递归函数来求解斐波那契数列的第n项的Python代码如下：

# recursive method
def fib(n):
    if n <= 1:
        return n
    else:
         return fib(n-1) + fib(n-2)

t = fib(10)
print(t)

  为了展示该递归方法的函数调用图，我们可以用graphviz模块来绘制该流程图。Graphviz （英文：Graph Visualization Software的缩写）是一个由AT&T实验室启动的开源工具包，用于绘制DOT语言脚本描述的图形。在Python中，它的实现模块为graphviz, 其API参考文档为： http://graphviz.readthedocs.io/en/latest/index.html 。
  下面将给出n=6时递归函数的调用图， Python代码如下：

from graphviz import Digraph
import uuid
import random

# colors for labels of nodes
colors = ['tomato', 'skyblue', 'orange', 'purple', 'green', 'yellow', 'gray', 'pink']

# n: the nth item in Fabonacci sequence
# dot: Digraph object
# label: label of each node
# parent: label of parent node
def fib(n, dot, label, parent):

    if n <= 1:
        return n, dot
    else:
        random.shuffle(colors)
        # create node with style='filled' and random color
        dot.node(label[0], 'fib(%s)'%(n-1),style='filled',color=colors[0])
        dot.node(label[1], 'fib(%s)'%(n-2),style='filled',color=colors[1])

        # connect the new created nodes with parent node
        dot.edge(label[0], parent)
        dot.edge(label[1], parent)

        # generate new label using uuid() function
        label1 = [str(uuid.uuid1()) for _ in label]
        label2 = [str(uuid.uuid1()) for _ in label]

        return fib(n-1, dot, label1, label[0])+fib(n-2, dot, label2, label[1]), dot

# test
dot = Digraph()
n = 6 # the nth item in Fabonacci sequence
label = ['a', 'b'] # initial labels
t, dot = fib(n, dot, label, parent='fib(%s)'%n)

# save the source code of dot to gv file
print(dot.source)
dot.render('E:\\fib_graph.gv')

  运行完上述程序后，会在E盘下生成fib_graph.gv文件，再用Graphviz软件打开，生成图片，如下：

注意：本人现已开通两个微信公众号： 用Python做数学（微信号为：python_math）以及轻松学会Python爬虫（微信号为：easy_web_scrape）， 欢迎大家关注哦~~