1

I want to write a program in Python that illustrates the tree-like nature of recursion. Given a recursive function (for instance fibonacci(n)) there should be a way to print the tree-like call trace of the recursive function. With the following function:

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

The print out for n=5 could look something like:

                             fibo(5)    
               fibo(4)                    fibo(3)
       fibo(3)         fibo(2)      fibo(2)        fibo(1)
 fibo(2)      fibo(1)           

The solution should be as "general" as possible and not specific to Fibonacci numbers as I want to implement it for additional recursive functions.

closed as unclear what you're asking by durron597, user22815, gnat, Matthew Flynn, user40980 Sep 17 '15 at 18:13

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • What you want to do is very similar to how tracing works. There is a Python module for that. – coredump Sep 17 '15 at 11:25
  • Unclear what help you need. Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it’s hard to tell what problem you are trying to solve or what aspect of your approach needs to be corrected or explained. See the How to Ask page for help clarifying this question. – gnat Sep 17 '15 at 14:10
  • If we can edit this to a point where this is a good question, I got a decorator that can print a call tree for recursive functions. – Harrichael May 11 '17 at 20:24
5

You can't just modify fibo to get what you want. For instance, the order in which the different calls to fibo happen is not the one in which you have to write their arguments to the console, and because you don't know the width of your tree to begin with, you don't know how far to the right to start with the root.

What you have to do is to collect the calls and their arguments in a temporary data structure as they happen, likely also a tree, and then traverse that data structure after the first recursion has terminated.

-2

You can pass another argument to the recursive function that starts from 0 and increments by 1 in every call in order to determine the depth of recursion tree. Then you can use stacks to store "function(x)" strings and finally print them according to depth.

e.g. fibo(5,0) -> fibo(4,1),fibo(3,1) -> fibo(3,2),fibo(2,2),fibo(2,2),fibo(1,2) ->...

  • Could you explain a bit more about this and how it differs from Kilian's answer? – user40980 Sep 17 '15 at 13:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.