Counting how many times a function is called recursively (Python)

Question

I am currently making a program that includes a recursive function that always returns 1. The function looks like this:

def fn(n):
    if n <= 1:
        return n
    elif n > 1 and n % 2 == 0:
        return fn(n/2)
    elif n > 1 and n % 2 > 0:
        return fn(3*n+1)

As I will be creating other functions, I need to create a function that counts how many times fn() is called recursively within the fn() function (How many calls does 'n' take to reach 1). I am able to do this using a global variable, however I am not sure how to do this using another recursive function. Any help would be appreciated. Thanks.

Answer 1

Why not add a second parameter to your function and increment that on recursive calls?

def fn(n):
    def _fn(n, calls):
        if n <= 1:
            return n, calls
        # n > 1 is a given by this point.
        return _fn(n / 2 if n % 2 == 0 else 3 * n + 1, calls + 1)

    return _fn(n, 1)

Answer 2

FWIW an arguably simpler option is to hold the count state inside the function itself, without having to nest it nor wrap it in a decorator.

This is akin to doing it thru a global variable, but with the added benefit of restricting the count to the function scope.

For instance:

def fn(n):
    try:
        fn.count += 1
    except AttributeError:
        fn.count = 1

    if n <= 1:
        return n
    elif n > 1 and n % 2 == 0:
        return fn(n/2)
    elif n > 1 and n % 2 > 0:
        return fn(3*n+1)

Output:

In [15]: fn(5)
Out[15]: 1.0

In [16]: fn.count
Out[16]: 6

PS: Your n > 1 check is unnecessary. You might simplify your function a bit by dropping it altogether:

def fn(n):
    try:
        fn.count += 1
    except AttributeError:
        fn.count = 1

    if n <= 1:
        return n
    return fn((3*n + 1) if n % 2 else (n / 2))