Python count iterations of recursive call

Question

I'm trying to count the number of times the collatz_chain() function is called recursively. In particular, the code below seems to set the count variable to 1 at the end (outside of the recursive calls) even though it is incremented correctly inside the recursive function.

def collatz_longest_chain(limit):
    iter = 1
    while(iter < limit):
        count = 0
        _next_num, count = collatz_chain(iter, count)
        iter += 1

    print('----')
    return count

def collatz_chain(n, count):
    if n == 1:
        count += 1
        print("n=1" + " count: " + str(count) + " | inside n == 1")
        return 1, count
    elif n % 2 == 0:
        count += 1
        print("n: " + str(n) + " count: " + str(count) + " | inside n % 2 == 0")
        return collatz_chain(n/2, count), count
    else:
        count += 1
        print("n: " + str(n) + " count: " + str(count) + " | inside 3*n + 1")
        return collatz_chain(3*n + 1, count), count

print(collatz_longest_chain(10))

The output is:

...
n: 9 count: 1 | inside 3*n + 1
n: 28 count: 2 | inside n % 2 == 0
n: 14.0 count: 3 | inside n % 2 == 0
n: 7.0 count: 4 | inside 3*n + 1
n: 22.0 count: 5 | inside n % 2 == 0
n: 11.0 count: 6 | inside 3*n + 1
n: 34.0 count: 7 | inside n % 2 == 0
n: 17.0 count: 8 | inside 3*n + 1
n: 52.0 count: 9 | inside n % 2 == 0
n: 26.0 count: 10 | inside n % 2 == 0
n: 13.0 count: 11 | inside 3*n + 1
n: 40.0 count: 12 | inside n % 2 == 0
n: 20.0 count: 13 | inside n % 2 == 0
n: 10.0 count: 14 | inside n % 2 == 0
n: 5.0 count: 15 | inside 3*n + 1
n: 16.0 count: 16 | inside n % 2 == 0
n: 8.0 count: 17 | inside n % 2 == 0
n: 4.0 count: 18 | inside n % 2 == 0
n: 2.0 count: 19 | inside n % 2 == 0
n=1 count: 20 | inside n == 1
----
1

How can I pass the correct count variable value out of the recursive call, so that the output would be:

...
n=1 count: 20 | inside n == 1
----
20

question from:https://stackoverflow.com/questions/65650033/python-count-iterations-of-recursive-call

Answer 1

In your base case you are returning a tuple and the count:

return 1, count

But in the recursive calls you are returning the result of the recursion (which is a tuple) and the count

return collatz_chain(3*n + 1, count), count
# collatz_chain already returns the count

so you end up returning a long nested tuple in _next_num. If you want the the final count returned, you need to return values from the recursive calls in the same shape as the base case with something like:

def collatz_chain(n, count):
    count += 1
    if n == 1:
        print("n=1" + " count: " + str(count) + " | inside n == 1")
        return 1, count
    elif n % 2 == 0:
        print("n: " + str(n) + " count: " + str(count) + " | inside n % 2 == 0")
        return collatz_chain(n/2, count)
    else:
        print("n: " + str(n) + " count: " + str(count) + " | inside 3*n + 1")
        return collatz_chain(3*n + 1, count)

This will print:

n: 20.0 count: 13 | inside n % 2 == 0
n: 10.0 count: 14 | inside n % 2 == 0
n: 5.0 count: 15 | inside 3*n + 1
n: 16.0 count: 16 | inside n % 2 == 0
n: 8.0 count: 17 | inside n % 2 == 0
n: 4.0 count: 18 | inside n % 2 == 0
n: 2.0 count: 19 | inside n % 2 == 0
n=1 count: 20 | inside n == 1
----
20

However, note that this is not the total calls to collatz_chain(). It is the number of recursive calls in the last invocation of your while loop.

If you want the total count you need to use the above changes and then take the total of all the calls from the while loop. Something like:

def collatz_longest_chain(limit):
    iter = 1
    total_count = 0
    while(iter < limit):
        count = 0
        print("calling iter: ", iter, count)
        _next_num, count = collatz_chain(iter, count)
        iter += 1
        total_count += count

    print('----')
    return count, total_count

One other note: iter is a built-in function in Python, so you probably shouldn't use it as a variable name. It will overwrite the built-in.