Can't understand the output of this recursion function

[bigmit37]

def f(n):
    if n < 5:
        return n + 1
    
    return (f(n // 2) ,  f(n // 3) ) 

f(100) is leading to an output of
(((((4, 3), 5), (5, 3)), ((5, 3), (3, 2))), (((5, 3), (3, 2)), ((3, 2), 4)))




I broke down the recursions like this:


f(50), f(33)
f(25), f(11)
f(12), f(3)
f(6), 4 #recursion stops
f(3), 4
4, 4

So I expected an outcome of (4,4)


However, I have no idea why I'm getting an output of

((((4, 3), 5), (5, 3)), ((5, 3), (3, 2))), (((5, 3), (3, 2)), ((3, 2), 4)))


Thank you.

[Ofnuts]

Recursion stops on one branch... but your code spawns a new branch on almost every call to f()

                                    100
                    50                               33
            25               16              16              11
        12     8        8        5        8        5       5      3
      6    4  4   2    4   2    2   1    4   2   2    1   2   1   4
     3 2   5  5   3    5   3    3   2    5   3   3    2   3   2
     4 3

[bigmit37]

Thank you! I finally understand. The recursion follows the left most branch and makes its way to the right.

[Ofnuts]

Thank you! I finally understand.  The recursion follows the left most branch and makes its way to the right.

Not really... that's just a representation. The recursion happens in all the branches independently of what happens in the others.

[bigmit37]

Thank you! I finally understand.  The recursion follows the left most branch and makes its way to the right.

Not really... that's just a representation. The recursion happens in all the branches independently of what happens in the others.

Sorry, I meant the output. The output seems to be following the path from left to right.

[Ofnuts]

levels=[[] for _ in range(10)]

def f(n,l):
    if n < 5:
        levels[l].append(n+1)
        return n + 1
    levels[l].append(n//2)
    levels[l].append(n//3)    
    return (f(n // 2,l+1) ,  f(n // 3,l+1) )

print f(100,0)

for l in levels:
    if l:
        print ' '.join(map(str,l))