The easiest way to produce unterstandable code in a situation like this is probably to follow @jonrshapre and modify the function itself. You can extend his solution with a helper function, which wraps the previous function so that the trace is printed as side-effect and only the actual Fibonacci is returned:
def fibonacci(n):
generator = fib(3)
final_answer = 0
for s in fib(3):
print(s)
final_answer = s
return int(final_answer)
But if you're already thinking in terms of wrapping functions, then you should really consider decorators. Decorators are really nothing more than syntactic sugar for wrapping other functions. A properly constructed decorator will allow to easily add a trace of sorts to any function. Here is a first attempt at one a possible solution (the output isn't quite as nice as what you wanted, but it does show the recursive call depth quite nicely):
import functools
def trace_recursive(combine,line_length=15):
def dec_wrapper(func):
@functools.wraps(func)
def func_wrapper(*args,**kargs):
positional = [str(a) for a in args]
keyword = ["{}={}".format(k, kargs[k]) for k in kargs]
call = ', '.join(positional + keyword)
call = "{}({})".format(func.__name__, call)
func_wrapper.depth = func_wrapper.depth + 1
func_wrapper.last_depth = func_wrapper.depth
return_val = func(*args,**kargs)
if func_wrapper.depth < func_wrapper.last_depth:
print "{}{}{}".format(func_wrapper.depth*' ',combine,line_length*'_')
call_and_value = "{}={:>5}".format(call,return_val)
indent = func_wrapper.depth * ' '
call_and_value = indent + call_and_value
print call_and_value
func_wrapper.depth = func_wrapper.depth - 1
return return_val
func_wrapper.depth = 1
func_wrapper.last_depth = 1
return func_wrapper
Once you have that decorator, you can apply it easily to any function:
@trace_recursive('*')
def fac(n):
if n in(0, 1):
return 1
else:
return n * fac(n-1)
A sample of the output:
>>> fac(4)
fac(1)= 1
*_______________
fac(2)= 2
*_______________
fac(3)= 6
*_______________
fac(4)= 24
24
Since you're dealing with Fibonacci numbers, you might want to think about memoization, i.e. saving previously computed values. The naive recursive implementation is otherwise quite wasteful, computing many values multiple times due to the twin recursive calls. You can implement memoization as a decorator -- there's a whole section at the Python Decorator Library and Active State has a particularly nice one, which they claim is probably the fastest memoization decorator. But we can implement a very simple one for functions of a single (hashable) argument:
def simple_memoize(func):
cache = dict()
@functools.wraps(func)
def wrapper(arg):
try:
return cache[arg]
except KeyError:
cache[arg] = func(arg)
return cache[arg]
return wrapper
So, let's take a look at the trace for the Fibonacci function without memoization:
@trace_recursive('+')
def fib(n):
if n in (0, 1):
return n
else:
return fib(n - 1) + fib(n - 2)
gives you:
>>> print fib(5)
fib(1)= 1
fib(0)= 0
+_______________
fib(2)= 1
fib(1)= 1
+_______________
fib(3)= 2
fib(1)= 1
fib(0)= 0
+_______________
fib(2)= 1
+_______________
fib(4)= 3
fib(1)= 1
fib(0)= 0
+_______________
fib(2)= 1
fib(1)= 1
+_______________
fib(3)= 2
+_______________
fib(5)= 5
5
And you can clearly see that each of the smaller Fibonacci numbers is computed multiple times. If we add memoization, then we get better results:
@trace_recursive('+')
@simple_memoize
def fib(n):
if n in (0, 1):
return n
else:
return fib(n - 1) + fib(n - 2)
Output:
>>> print fib(5)
fib(1)= 1
fib(0)= 0
+_______________
fib(2)= 1
fib(1)= 1
+_______________
fib(3)= 2
fib(2)= 1
+_______________
fib(4)= 3
fib(3)= 2
+_______________
fib(5)= 5
5
BTW: decorator order is generally speaking non commutative. Each decorator wraps the complete decorated function it's sitting on top of, i.e. the uppermost decorator is the outermost. We can see this in our example:
@simple_memoize
@trace_recursive('+')
def fib(n):
if n in (0, 1):
return n
else:
return fib(n - 1) + fib(n - 2)
Output:
>>> print fib(5)
fib(1)= 1
fib(0)= 0
+_______________
fib(2)= 1
+_______________
fib(3)= 2
+_______________
fib(4)= 3
+_______________
fib(5)= 5
5
Although the memoization is equally effective in both cases, in the inner memoization case, the trace is printed before the memoization functions shortcuts to the cache, while in the outer memoization case, the shortcutting to cache completely block the inner calls so that the trace decorator is never called.
