double recursive education example

Question

This function is just not making sense to me. Ive added print statements all over the place to figure out whats going on and I still dont get it. I'd be grateful if someone could explain this to me.

def f(s):
    if len(s) <= 1:
        return s
    return f(f(s[1:])) + s[0]

print(f("mat"))

This is what I see happening. So we start with string of length 3 and bypass the if statement. We work on the inside f(s[1:]) first. So now we have a string of length 2 ("at") that again bypasses the if statement and enters the f(s[1]) which gives us string of length 1 ("t") that enters the if statement finally and returns "t". This is where the trail goes cold for me.

From my print statements, I see a new string of length 2 is created and subsequent "a" gets returned. The final product ends up being "atm". I get the "m" being tagged on the end thanks to the "+ s[0]" part but why is it "atm" and not "tam"?

I've honestly spent a few hours on this and cant make it rain. Any help would be appreciated.

Answer 1

Expand the whole thing out into long steps by filling in the function calls with what they are doing. Deal with the brackets from the deepest/most embedded first. Deal with function calls before addition.

I'm going to ignore the string quotes everywhere for clarity.

f(mat)           -> mat is 3 chars:
                    call f on at for f(at), and call f on that.
                    add m.

f(f(at))+m       -> inner f(at), at is 2 chars:
                    call f on t for f(t), and call f on that.
                    add a.

f(f(f(t))+a)+m   -> innermost f(t) returns t.

f(f(t)+a)+m      -> inner f(t) returns t as well.

f(ta)+m          -> [here, the first f(f(at)) has been reduced to f(ta)]
                    ta is 2 chars:
                    call f on a for f(a), and call f on that.
                    add t.

f(f(a))+t+m      -> inner f(a) returns a.

f(a)+t+m         -> f(a) returns a as well.

a + t + m        -> 

atm              -> everything reduces to atm.

Answer 2

Short version: the a and t are getting swapped twice, so the inner f("at") call returns "ta", then the outer f() call gets passed "ta" and returns "at".

Longer version: I won't spell it out explicitly for you since you won't learn as much that way, but consider this function, which is totally equivalent:

def f2(s):
    if len(s) <= 1:
        return s
    x = f2(s[1:])
    return f2(x) + s[0]

print(f2("mat"))

When you call f2("mat"), s[1:] is "at". Now, what does f2("at") return? Plug that value (the value of x) into the f2(x) + s[0] expression and see what you get.

Try running through the values of f2("at") and f2("ta") and see if you can spot what's happening. If you still need help after another 15-20 minutes of work, comment on this answer and I'll expand on it some more.