user3419211 user3419211 - 9 months ago 46
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 Source

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