Question

Can someone explain double recursion? Why does this print hatm instead of htam?

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

Answer 1

http://codepad.org/H4repj9b
just testing with single, seems get htam
def f(s):
if len(s) <=1:
return s
return f(s[1:])+s[0]
print f('math')

Answer 2

you can see the problem here, i think because of double recursion, th become ht

http://codepad.org/krTpnr42

s0=math
s1=ath
s2=th
s3=ht
s4=tha
s5=ha
s6=ah
s7=hatm

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

Answer 3

dun know why, im still not very comfortable to use recursions..

Answer 4

Ahhh sorry I should have left the print s out of the function. I understand that f(s[1:]) will continually unfold the list until it has len 1. So...whether s is 'math' or 'recurisionmath' it will always unfold until it's just left with h even if u has f(f(f(s[1:]))).

The part that I'm stuck on is this +s[0]

You would think it would unfold as
s0=math
s1=ath+m
s2=th+a+m
s3=h+t+a+m

Answer 5

still reading some docs but i guess when you run return f(f(s[1:]))+s[0]
you have to conside the f( f(s[1:]) )+s[0]
s0-1 = f( f ( ath) ) + m
s0-2 = f( f (th) + a ) + m

i think its little different than you expected..
if anyone have a clear understanding plz update..

Answer 6

you are on the right track callmejon
the + s[0] takes the first letter of the string and puts it at the end - the rest of the string gets passed in the recursion. when you get down to two letters they are effectively swapped

aybe?
reverse the word - t h a m
reverse the first three letters of that result - a h t m
reverse the first two letters of that result - h a t m
string them all together

with the print statement at the 'top' you can see what is being passed (and returned?) on each recursion -
going from one line to the next and having less letters is going 'down' the stack and going from line to line and getting more letters is going 'up' the stack:
4 letters: http://codepad.org/LqcGMkyU
5 letters: http://codepad.org/3DFco7rw

Answer 7

thanks bwCA, i think i got it.
step0 = f0(math)
step1 = f0( f1 (ath) )+m
step2 = f0 ( f1 (f2 (th) +a) +m
step3 = f0 ( f1 (f2 (f3(h) +t ) +a) + m
working out
f3= h
f2 = ht
f1 = tha
f0 = hatm

hope this is making sense...