开发者社区> jclian91> 正文

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

简介:   在博客动态规划法(一)从斐波那契数列谈起中,在求解斐波那契数列的第n项时,我们采用了递归方法和动态规划法来求解,当然递归方法的效率很差。
+关注继续查看

  在博客动态规划法(一)从斐波那契数列谈起中,在求解斐波那契数列的第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), 欢迎大家关注哦~~

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【C语言】函数递归实现——扫雷小游戏(详细步骤)
【C语言】函数递归实现——扫雷小游戏(详细步骤)
34 0
Java中函数的递归调用
说到递归,java中的递归和C语言中也是很相似的,在Java中,递归其实就是利用了栈的先进后出的机制来描述的。 public class HelloWorld { public static void main(String[] args){ // Scanner s = new Scanner(System.
724 0
Python语言学习:基于python五种方法实现使用某函数名【func_01】的字符串格式('func_01')来调用该函数【func_01】执行功能
Python语言学习:基于python五种方法实现使用某函数名【func_01】的字符串格式('func_01')来调用该函数【func_01】执行功能
52 0
javascript函数的递归调用问题
functin(arg) { var arg2 = ....; arguments.callee(arg2); ... }
523 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
19696 0
函数调用运算符
14.34定义一个函数对象类,令其执行if-then-else的操作;该类型的调用运算符接受三个参数,它首先检查第一个形参,如果成功返回第二个参数的值;如果不成功返回第三个形参的值。 #include using namespace std; class if_then_else { ...
677 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
17986 0
2014秋C++ 第12周项目 C++函数新特征与递归函数
课程主页在http://blog.csdn.net/sxhelijian/article/details/39152703,课程资源在云学堂“贺老师课堂”同步展示,使用的帐号请到课程主页中查看。  【项目1- 阅读程序】阅读下列程序,写出程序的运行结果。上机时运行程序,与你的预期进行对照、理解。如果对运行结果和其背后的原理仍不理解,请通过单步执行的手段跟踪理解。(1)阅读下面两个有静态局部变量
1145 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
24792 0
Windows的程序性能分析和函数呼叫列表工具LTProf (Call Graph at Runtime)
转载请注明出处:http://blog.csdn.net/horkychen  GNU有一个强大的性能分析工具gprof,同时可以输出程序调用顺序。
867 0
+关注
jclian91
热爱算法,热爱技术,热爱生活,期待更好的自己与明天~
126
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载