user3419211 user3419211 - 24 days ago 7
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?

Answer

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