Can someone explain double recursion python?

Question

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:

4. d + l = dl
5. dl + r = dlr
6. dlr + o = dlro
7. 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?

Answer 1

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