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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

jclian91 2018-06-01 14:31:55 浏览615
展开阅读全文

  在博客动态规划法(一)从斐波那契数列谈起中,在求解斐波那契数列的第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软件打开,生成图片,如下:


n=6的递归函数调用图

  本次分享仅作为graghviz模块的一个例子,欢迎广大读者能提供更多例子~~
  本次分享到此结束,欢迎大家交流~~

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

网友评论

登录后评论
0/500
评论
jclian91
+ 关注