user3419211 - 1 year ago 66
Python Question

# Can someone explain double recursion python?

Im trying to understand double recursion but i'm not getting anywhere.

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

dlrow

if am right the above code will do the following:

1. f(s[1:]) + s[0] ==> f(orld) + w

2. f(s[1:]) + s[0] ==> f(rld) + o

3. f(s[1:]) + s[0] ==> f(ld) + r

4. f(s[1:]) + s[0] ==> f(d) + l <== here len(s) == 1 so s = d,

then:

1. d + l = dl

2. dl + r = dlr

3. dlr + o = dlro

4. dlro + w = dlrow

so dlrow will be printed as seen above.

I can not understand the code when you make it double recursive:

``````def f(s):
if len(s) <= 1:
return s
else:
return f(f(s[1:])) + s[0] #Note double recursion
print f('world')
``````

Can someone please explain to me how this double recursion works?

Here's an easy way to instrument your recursive code

``````import inspect

def f(s):
print "  " * (len(inspect.stack())-2), '>>', s
if len(s) <= 1:
print "  " * (len(inspect.stack())-2), '<<', s
return s
else:
retval = f(f(s[1:])) + s[0] #Note double recursion
print "  " * (len(inspect.stack())-2), '<<', retval
return retval

print f('world')
``````

prints

`````` >> world
>> orld
>> rld
>> ld
>> d
<< d
>> d
<< d
<< dl
>> dl
>> l
<< l
>> l
<< l
<< ld
<< ldr
>> ldr
>> dr
>> r
<< r
>> r
<< r
<< rd
>> rd
>> d
<< d
>> d
<< d
<< dr
<< drl
<< drlo
>> drlo
>> rlo
>> lo
>> o
<< o
>> o
<< o
<< ol
>> ol
>> l
<< l
>> l
<< l
<< lo
<< lor
>> lor
>> or
>> r
<< r
>> r
<< r
<< ro
>> ro
>> o
<< o
>> o
<< o
<< or
<< orl
<< orld
<< orldw
orldw
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download