Debugging recursive function to se how many times it repeats a certain calculation

Question

I have a fibonacci series defined by a recursive function. My assignment is to debug to see how many times the function repeats certain calculations when called. How many times does fib(3) needs to be calculated when calling fib(10).

I have tried to use the pycharm debugging tool but it gets me nowhere. I start by adding a breakpoint in the beginning of the code and clicked debug. Then i tried to follow the code step by step, by the step over f8. Is there some other ways to solve this other than using pycharm?

        if n < 3:
            return 1
        else:
            return fib(n-1) + fib (n-2)

Mert Köklü · Answer 1 · 2019-10-08T14:48:22.123

3

You can create a global variable and assign it to zero. After calling your recursive function you can look the value of your repeat variable.

repeat = 0  # you need to declare outside of function

def recursive_function(n):
    global repeat # you need to use 'global' keyword in order to modify global variable
    repeat += 1
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1) + fib (n-2)

recursive_function(7)
print(repeat)
# call tree looks like this:
#                  fib(5)  
#          fib(4)    +    fib(3)
#    fib(3) + fib(2)    fib(2) + fib(1)
#fib(2)+fib(1)

edited Oct 08 '19 at 14:48

answered Oct 07 '19 at 12:05

Mert Köklü

2,183
2
16
20

Thank you for your answer, but i get a UnboundLocalError: local variable 'repeat' referenced before assignment error. – SlowPace Oct 08 '19 at 02:05
If you want to use a global variable inside a function, you must use the global keyword. I have edited my answer. I am sorry that i have skipped that line. – Mert Köklü Oct 08 '19 at 10:11
It was my mistake, i just want to ask one more thing. I have some difficulty understanding how the global variabel repeat relates to the recursive function. For recursive_function(5), when the function is called global is assigned the value 1, 5 > 3 gives recursive_function(4)+recursive_function(3) 2 more calls, how does repeat change? The value of repeat is 9 for recursive_function(5) what does that mean exactly? Thank you very much for replying. – SlowPace Oct 08 '19 at 13:35
I think you are struggling with understanding how recursion works. I have edited my answer in order to explain how call tree looks like. Whenever you call fib function `repeat` variable increments by 1. So if you call fib(5) in first place, call tree looks like above and `repeat` variable equals to 9 after recursion done because we are entering `fib` function 9 times. If you want to understand deeply you can add breakpoint in `repeat += 1`, debug the code and watch how `repeat` variable changes. – Mert Köklü Oct 08 '19 at 14:57
I will leave you with a link to understand recursion. (https://stackoverflow.com/questions/11693819/understanding-recursion-in-python) – Mert Köklü Oct 08 '19 at 14:57
Hi SlowPace, In the answer above the `repeat` global variable will be incremented each time `recursive_function()` is called, so if you look at the nice tree Marceline made there are 9 total calls, which `repeat` has counted. Your specific question asks to count the calls to `fib(3)` specifically, this can be accomplished by putting the `repeat +=1` behind an if statement: `if n==3:` – Hoog Oct 08 '19 at 15:01

score 1 · Answer 2 · answered Oct 08 '19 at 10:36

You can define a decorator to log function calls:

from functools import wraps

def log_calls(func):
    @wraps(func)
    def logged(*args):
        print(f'call {func.__name__}({", ".join(map(repr, args))})')
        return func(*args)
    return logged

Instead of printing, you can of course also increment a counter or use a different means to track progress. You can also do the printing conditionally, e.g. if args equals 3.

Applying this decorator to your function makes all calls visible:

@log_calls
def fib(n):
    return 1 if n < 3 else fib(n - 1) + fib(n - 2)

For example, fib(5) calls fib(3) twice:

>>> fib(5)
call fib(5)
call fib(4)
call fib(3)
call fib(2)
call fib(1)
call fib(2)
call fib(3)
call fib(2)
call fib(1)

Debugging recursive function to se how many times it repeats a certain calculation

2 Answers2

Linked