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

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

Thanks gribbler, i didn't know about inspect. everything becomes easier when visualized.
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.
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.
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

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'))

Collectives™ on Stack Overflow

Can someone explain double recursion python?

2 Answers 2

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Related