I don't understand recursion

Question

I can understand simple recursion, such as:

def count(n):
    if n <= 0:
        return
    else:
        print n
        count(n-1)

count(3)

However, when faced with more complicated code, such as, an implementation of Koch snowflake:

def koch(order, size):
    if order == 0:
            t.forward(size)
    else:
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)
            t.right(120)
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)

koch(1, 100)

I get confused. I do not understand how to follow these multiple recursive function calls.

To understand recursion, first you must understand recursion. — Ernest Friedman-Hill, Jul 19 '13 at 11:37
practice practice and keep practicing... until u start understanding. — Zaheer Ahmed, Jul 19 '13 at 11:38
note that in most cases an iterative algorithm is the better approach. It won't need the stack and extra function calls. And there is a rule: Every recursion can be replaced by iteration. So, search for the iterative ones if you wanna have fun! :) Like [this](http://www.metashock.de/2013/07/iterative-algorithm-to-remove-a-directory-tree/) — hek2mgl, Jul 19 '13 at 11:43
@hek2mgl, but the iterative approach is prone to accumulation of floating point errors. It's easier to circumvent with the recursive approach. — John La Rooy, Jul 19 '13 at 11:52
First you need to know what is this t. Looks like the algorythm moves it forward, then changes direction, move one third forward, changes direction again, moves a thirr of a third....and so on, until order is 0. But it seems you should have not a single t, because there's not just one arm to increase, but lots of arms over arms. — Daniel Möller, Jul 19 '13 at 11:56
@gnibbler I like your comment, but don't understand it so far. can you give a link which demonstrates the problem? — hek2mgl, Jul 19 '13 at 12:11
possible duplicate of [Understanding recursion](http://stackoverflow.com/questions/717725/understanding-recursion) — ethan, Jul 19 '13 at 12:25
@hek2mgl, you mean the floating point errors? If you run `koch` to enough levels, you will finish up at a slightly different point that if you run only one or a few levels deep. — John La Rooy, Jul 19 '13 at 12:26
@gnibbler please explain. I'm not a python expert, but the topic should be general. Please explain also the advantage to iterative algorithms.. My poor understanding tells me that recursion is always limited because of the stack.. would really like to get teached — hek2mgl, Jul 19 '13 at 12:36
@hek2mgl, It's not Python specific. Do you understand that there are errors due to loss of precision when adding small floating point numbers to large ones? — John La Rooy, Jul 19 '13 at 12:54
@gnibbler Seems that I don't understand that currently as I didn't had a deeper look into `koch()`. But now I understand that you are pointing more to the `koch()` function than to general recursion. I've had in mind recursion in general when writing comments. — hek2mgl, Jul 19 '13 at 12:58
Also see http://stackoverflow.com/questions/17745148/i-dont-understand-recursion — llb, Jul 19 '13 at 13:33

score 2 · Accepted Answer · answered Jul 19 '13 at 11:41

2

I don't think it's especially easy for anyone to visualize the execution path in detail in their head. Drawing a tree, with the nodes representing the individual recursive calls, is a good way to visualize it on paper. If each node is a bubble, you can put information about variable states, etc., in them. In the situation where there are multiple recursive calls, each node will have multiple trees under it, representing a timeline.

answered Jul 19 '13 at 11:41

Ernest Friedman-Hill

80,601
10
150
186

This is how I ended up grasping it, thanks! – Nathan Jul 31 '13 at 06:43

score 2 · Answer 2 · answered Jul 19 '13 at 11:48

Your Koch snowflake example is a good one. What does the snowflake consist of? In the first iteration (order == 0), it starts out as a simple line. This is the base case.

________

Now, for the next level of recursion (order == 1), that base case is split into four sub-lines that form an inverted V. To achieve this V, you need to build four lines at the appropriate angles to each other (for which you need the t.left(60) and similar commands).

Each of these lines is (regarded by itself) an instance of the base case, again. It's just three times smaller. That's what you see in koch(order-1, size/3).

   /\
__/  \__

Now imagine the next level of recursion - each line is again split up into four sublines. The pattern continues...

score 2 · Answer 3 · answered Jul 19 '13 at 11:54

For koch(1, 100) it will look like this:

koch(1, 100)
->
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
    t goes left
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
    t goes right
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
    t goes left
    koch(0, 33)
      order == 1, so stop recursing down this branch
    <-
<-
done

For koch(2, 100) the first call to koch will then expand out to the above,

koch(2, 100)
->
    koch(1, 100)
    ->
        koch(0, 33)
          order == 1, so stop recursing down this branch
        <-
        t goes left
        ...
    ...
    t goes left
    ...

Try to trace it out on paper as has been suggested. You will end up with a tree like structure.

score 1 · Answer 4 · edited Jul 19 '13 at 13:21

Try, something along the lines of:

def koch(order, size):
    print 'koch(', order, size, ')'
    if order == 0:
            t.forward(size)
            print 'Got to the bottom of it'
    else:
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)
            t.right(120)
            koch(order-1, size/3)
            t.left(60)
            koch(order-1, size/3)

koch(1, 10)

And you should see how each call calls koch until it finally gets to the bottom of the chain.

score 1 · Answer 5 · answered Jul 19 '13 at 12:09

1

The python tutor web site can help in visualising program flows http://www.pythontutor.com/

answered Jul 19 '13 at 12:09

Steve Allison

1,091
6
6

score 0 · Answer 6 · answered Jul 19 '13 at 11:45

To understand the code it helps to have a look at the first steps of creating a koch snowflake. In every recursion step you have a triangle, an the code overlays anotherone. Now you have new triangles for which the code is called - and everything starts from beginning.

I don't understand recursion

6 Answers6