Trouble understanding recursion (Python)

[mrcleanhands]

I'm trying to understand a function which draws a koch curve using a library which draws (lt = left turn, fd = move forward, t represents an object class).

def koch(t, n):
    if n<3:
        fd(t, n)
        return
    m = n/3.0
    koch(t, m)
    lt(t, 60)
    koch(t, m)
    rt(t, 120)
    koch(t, m)
    lt(t, 60)
    koch(t, m)

So let's say I start with n = 60, then m=20 and it executes koch(t, 20), but it will never get below koch(t,m) as if the number is above 3 then it keep returning to execute itself again. This is the way I see the code:

def koch(t, n):
    if n<3:
        fd(t, n)
        return
    m = n/3.0
    koch(t, m)
   DEAD CODE...

I'm confused what happens at this point. Does it continue executing the code right until the last line and then executes each koch(t,m) call separately?

 

[TylerH]

That's what it looks like to me. Have you ran it?

 

[rcgldr]

If n < 3, then koch() calls fd(), not koch(). Otherwise it sets m = n / 3, and makes calls to koch(m,...) (so m will eventually be < 3).

 

[dkMft]

I'm trying to understand a function which draws a koch curve using a library which draws (lt = left turn, fd = move forward, t represents an object class).

def koch(t, n):
    if n<3:
        fd(t, n)
        return
    m = n/3.0
    koch(t, m)
    lt(t, 60)
    koch(t, m)
    rt(t, 120)
    koch(t, m)
    lt(t, 60)
    koch(t, m)

So let's say I start with n = 60, then m=20 and it executes koch(t, 20), but it will never get below koch(t,m) as if the number is above 3 then it keep returning to execute itself again.


This is the way I see the code:

def koch(t, n):
    if n<3:
        fd(t, n)
        return
    m = n/3.0
    koch(t, m)
   DEAD CODE...

I'm confused what happens at this point. Does it continue executing the code right until the last line and then executes each koch(t,m) call separately?

If n<3 is your "base case". It is not defined here what fd() does, but the important thing is that the recursion tree for Koch() stops here. During the execution of Koch() n will never grow, so you are guaranteed that the base case will be hit at some point.

The code below koch(t,m) is not dead code! The recursion tree for Koch(t,m) just needs to bottom out and hit its own base case before returning. Once it does the execution continues as expected, with more Koch() calls and more recursions. They will eventually all stop though.

Edit: To help you visualize what happens, draw a tree for the execution of Koch() with relatively simple values.

Let's say we start with n = 18. Your tree will have a top-most node, where n = 18. Below it will be four nodes connected with lines, each with n = 18/3 = 6. Now each of those four nodes will again have four children (so 4*4=16 children at level 2) and n = 2. Now the tree stops, since n < 3.

To follow the program flow, start at the top and trace the tree down. Start with the leftmost child of the root. Since this child has a leftmost child of its own, trace that line down too. Now you should be at level 2 of the tree in the far left part. What happens now is that the program hits its base case, and starts returning again. So you trace up one node, and follow the line of the second child (the right next to the one you visited before).
This continues until all the child nodes have been visited, in which case you trace back up one level and continue from there with the rest of the un-visited child nodes.

 

[AlephZero]

I think you are confusing "calling the function recursively" with "jumping back to the top of the function". They are not the same thing.

You might want to try running something like this (I'm not a Python user so apologies for any syntax errors!)

def koch18(t, n):
    m = n/3.0
    koch6(t, m)
    lt(t, 60)
    koch6(t, m)
    rt(t, 120)
    koch6(t, m)
    lt(t, 60)
    koch6(t, m)
    return

def koch6(t, n):
    m = n/3.0
    koch2(t, m)
    lt(t, 60)
    koch2(t, m)
    rt(t, 120)
    koch2(t, m)
    lt(t, 60)
    koch2(t, m)
    return

def koch2(t, n):
   fd(t, n)
   return

That code is not recursive. Put some "print" statements so you can see how works when you do "koch18(t,18)".

That version of the code isn't very clever, because obviously "koch18" and "koch6" are almost exactly the same. The point of the recursive version is that you can replace them (and every other "koch..." function) with just ONE function, which calls itself.

Put some print statements in the original version, and compare what "koch(t, 18)" and "koch18(t,18)" do.