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:

f(s[1:]) + s[0] ==> f(orld) + w
f(s[1:]) + s[0] ==> f(rld) + o
f(s[1:]) + s[0] ==> f(ld) + r
f(s[1:]) + s[0] ==> f(d) + l <== here len(s) == 1 so s = d,

then:

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

Have you tried it? What happened? Why not try drawing the same diagram again? — jonrsharpe
– jonrsharpe, Commented Dec 3, 2014 at 22:45
The double recursion prints "orldw". the problem is, that i cannot draw a diagram for it.. — Ranj
– Ranj, Commented Dec 3, 2014 at 22:49
You see how long your analysis of the original version is? I assume the analysis of the second version will be twice as long ;-) — Alfe
– Alfe, Commented Dec 3, 2014 at 22:51
Princeton has this fantastic visualization of recursion using the Fibonacci sequence: introcs.cs.princeton.edu/java/23recursion — nonamorando
– nonamorando, Commented Dec 3, 2014 at 22:52
I suggest you start from the base case: what does calling the function on it twice do? Then build "out". Note that y = f(f(x)) is temp = f(x); y = f(temp). — jonrsharpe
– jonrsharpe, Commented Dec 3, 2014 at 22:54

John La Rooy · Accepted Answer · 2014-12-03 23:05:44Z

4

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

answered Dec 3, 2014 at 23:05

John La Rooy

306k54 gold badges378 silver badges513 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ranj Over a year ago

Thanks gribbler, i didn't know about inspect. everything becomes easier when visualized.

Alfe Over a year ago

But the question "what does this function do" remains. For "world" it returns "orld" + "w". But for other lengths the returned value is more complex. The most peculiar thing I just found out is that f(f(f('123'))) returns '123', f(f(f(f('1234')))) returns '1234' etc. for lengths up to 8. But f(f(f(f(f(f(f(f(f('123456789'))))))))) suddenly returns '283145796'. This is most peculiar.

Ranj Over a year ago

yes you're right! I was trying the same with "world". I have to play around with it, I will definitely come back to it after i understand what it does.

Alfe Over a year ago

Good luck. Seems to be a very complex topic. Have a look at pastebin.com/7fbcXZFc where I tried around a little bit.

equalizer · Accepted Answer · 2019-05-21 14:01:52Z

1

In 2019, using online compilers, such as www.onlinegdb.com/online_python_compiler, the print lines as above do not work. Here is working 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'))

answered May 21, 2019 at 14:01

equalizer

1562 silver badges10 bronze badges

Collectives™ on Stack Overflow

Can someone explain double recursion python?

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related