How to find number of subtractions in a recursive function-CodePudding

Here's the code:

def f(k):
    if k<3:
        return 1
    return f(k-1) f(k-2) f(k-3)

Thanks in advance!

CodePudding user response：

You could write a decorator to count calls to the function:

def count(func):
    def wrapper(*args, **kwargs):
        if kwargs.pop("reset", False):
            wrapper.calls = 0
        wrapper.calls  = 1
        return func(*args, **kwargs)
    wrapper.calls = 0
    return wrapper
    
@count
def f(k):
    if k<3:
        return 1
    return f(k-1) f(k-2) f(k-3)

Now you can count function calls:

>>> f(5, reset=True)
9
>>> f.calls
13
>>> f(23, reset=True)
532159
>>> f.calls
798251

CodePudding user response：

I got the same output as @schwobaseggl by using global variable:

count = 0
def f(k):
    global count
    count =1
    if k<3:
        return 1
    
    return f(k-1) f(k-2) f(k-3)
print(f(23))
print(count)