Understanding recursion in Python 2 (Think Python, exercise 5)

Question

I'm going through Think Python and I've reached recursion which is turning to be a great pain to understand for me.

There's this exercise, number 5, that shows me this piece of code:

def draw(t, length, n):
    if n == 0:
        return
    angle = 50            #sets angle
    fd(t, length*n)       #make a turtle() "t" go forward length*n pixels while drawing
    lt(t, angle)          #makes turtle "t" turn left on itself "angle" (50) degrees
    draw(t, length, n-1)  #1st call
    rt(t, 2*angle)        #makes turtle "t" turn right "2*angle" (100) degrees
    draw(t, length, n-1)  #2nd call
    lt(t, angle)          #makes turtle "t" turn left "angle" (50) degrees
    bk(t, length*n)       #makes turtle "t" go backwards length*n pixels

And asks me to think of what it does and then run it. I ran it and I had trouble understanding why it does what it does. It is a much more complex case of recursion that the ones the books presented for explaining this device and I cannot understand it. Lets make n for example 2 in order to understand a simple instance of this problem: What I can make out is that the code calls itself until n=0 up to the first call consecutively, then returns the control to n=1 and makes the remaining lines of code from call 1 to call 2. It makes the second call with n=0 and returns but I cannot understand what instance of the function it returns the control of the program. I'd be glad if someone could point me in the right direction as how to think this kind of recursive code by myself, how can I make use of it (when a for statement wouldn't quite make it) and a way to schematize the way it works (with some sort of diagram, for example?). I have this:

function called with n=2
 function called with n=1
  function called with n=0; returns to:
 function called with n=1 makes the 2nd call to the function with n=0
  function called with n=0; returns to where?
??????

As you can see it is quite impractical for, let's say, a function call with n = 7.

Martijn Pieters · Accepted Answer · 2014-01-10 16:36:14Z

A function always returns directly to its caller. Your recursive function does some work, calls itself, then when the call returns, does some more work, then calls itself another time, then when that returns, does some final work, before the function ends and itself returns:

work
call
work
call
work
return

That is, unless n == 0 is true, then the function immediately returtns. Every recursive call subtracts 1 from n so as long as n was positive to start with, your recursion ends at some point.

Recursion is simply the act of running the same function again, so you can substitute each call in the above 'diagram' with the same jobs being executed. Lets do this once:

n = 2
work
    n = 1
    work
    call
    work
    call
    work
work
    n = 1
    work
    call
    work
    call
    work
    return
work
return

I've added in the value for n, provided we start with n = 2. Of course, once you get down to n = 0, the call immediately returns; we can fill that in too:

n = 2
work
    n = 1
    work
        n = 0
        return
    work
        n = 0
        return
    work
    return
work
    n = 1
    work
        n = 0
        return
    work
        n = 0
        return
    work
    return
work
return

Now we have the full call tree for your recursive function, for n = 2. For higher values of n, just keep indenting and filling in the work - call - work - call - work - return lines anywhere there is a call line for the previous level, and you can build a full call tree for any recursive function.

Omar BISTAMI · Accepted Answer · 2016-10-11 10:00:04Z

1

So I've met the same issue to understand this exercice and i think there is nothing better than a schema or a picture to easily understand it , so here is my explanation for the first iteration of the code (using this same logic you'll understand the rest of the code easily) :

answered Oct 11, 2016 at 10:00

Omar BISTAMI

8502 gold badges12 silver badges22 bronze badges

Collectives™ on Stack Overflow

Understanding recursion in Python 2 (Think Python, exercise 5)

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related