Python101 Python101 - 4 months ago 24
Python Question

Outcome of double-recursion in Python

I have a question regarding these lines of code. I was trying to figure out what the print statement would show:

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


I was expecting it to print: "dcba",
but instead it showed: "dbca".
I would really appreciate if someone could explain to me why exactly this is happening. My goal is not to change to code in a way that it prints "dcba" but just to understand why it is behaving like it is. Thanks in advance for every help provided.
Cheers

Answer

I haven't ran your code through a debugger so I can't exactly see the stack trace, but it is due to you recursively calling f() twice. This seems over-manipulate the string leading to an unintended transformation. If you want to reverse a string recursively, the code below is fairly popular:

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

Sample Outcome:

print f("abcd")
>>> dcba