为通用递归程序生成递归树的程序 [英] Program to generate recursion tree for generic recursive program

问题描述

通常在解决递归或动态规划问题时，我发现自己画了一个递归树来帮助我简化问题.但是，对于一些复杂的问题，我可以访问解决方案，但不知道如何绘制树.

到目前为止我所尝试的是打印出调用函数及其参数，这在一些示例中被证明是有帮助的.但是，我在这个答案中看到了由 mathematica 在这里生成的 fibonacci(5) 树:

我想知道是否可以使用 Python、Java 或 C++ 等主流高级语言生成相同类型的树?树可以像图像中那样将节点作为函数名称和参数.

解决方案

我制作了一个简单的 Python 包，名为

查看更多示例

Often when solving a recursive or dynamic programming problem, I find myself drawing a recursion tree to help simplify the question for me. However, for some questions which are complicated I have access to the solution but no idea how to draw the tree.

What I have tried so far is printing out the calling function and it's parameters, and this has proved helpful in some examples. However, I saw this tree for fibonacci(5) here generated by mathematica in this answer: https://mathematica.stackexchange.com/questions/116344/how-do-i-create-a-recursive-tree-plot-for-the-fibonacci-sequence

I was wondering if I could generate the same kind of tree in a mainstream high level language like Python, Java, or C++? The tree could just have the nodes as the function name and parameters like in the image.

解决方案

I’ve made a simple python package called recursion-visualiser which you can install via pip that helps you to easily trace function calls for any arbitary recursive function and save tree as gif and png image by simply adding a decorator to your function.

Let's draw the tree for recursive Fibonacci function. Here is the recursive code:

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

def main():
    # Call function
    print(fib(n=6))

if __name__ == "__main__":
    main()

Now let's modify the code to draw recursion tree. First let's draw a very minimalist example

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

# Add decorator
@vs()
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()

The output file is saved as fibonacci.gif and fibonacci.png. Here is how output animation looks: Also the final image of recursion tree:

We can also make it better using node color and other properties:

# 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()

Here is the output which looks much better:

Here is the final image of the recursion tree:

Check out more examples at here

这篇关于为通用递归程序生成递归树的程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！