Hilbert Curve Analysis

Question

I'm just starting to learn Python and I don't understand the ability of calling the same function inside itself?

Here is an example:

import turtle
from turtle import left, right, forward

size = 10

def hilbert(level, angle):
    if level == 0:
        return

    turtle.color("Blue")
    turtle.speed("Fastest")

    right(angle)
    hilbert(level - 1, -angle)
    forward(size)
    left(angle)
    hilbert(level - 1, angle)
    forward(size)
    hilbert(level - 1, angle)
    left(angle)
    forward(size)
    hilbert(level - 1, -angle)
    right(angle)

How exactly does this work?

Thanks.

Answer 1

It's pretty simple actually. Speaking generally, and leaving out a few (important, but not to this discussion) exceptions:

• A function is a list of instructions, that operate on data.
• Part of that data is the "stack" - a block of memory
• Functions keep track of which PART of the stack is in use with a "stack pointer"
• When a function is called, the stack pointer is moved, and instructions act on the current stack pointer (perhaps moving it further)
• When a function finishes (returns), the pointer moves back.
• When a function calls another function, it moves the stack pointer, just as before.
• So, when a function calls itself, it's no different: the function pointer moves, then the function is executed.

In other words, the computer doesn't really care if you call different functions, or call the same function recursively. In fact, it can optimise the recursive function a little, because it knows the same things will happen each time, like a for loop.

Answer 2

I couldn't accept that the beauty of recursion was not understanding it, nor could I accept the fact that I might not be able to understand it myself! So after consulting a friend, I finally became aware of how the stack works. Here is my equivalent code for the Space Filling Hilbert Curve if level = 2 and angle = 90°:

import turtle
from turtle import left, right, forward

size = 10
angle = 90

turtle.hideturtle()
turtle.color("Blue")
turtle.speed("Fastest")

''' Assume we have two levels. '''

right(angle)

# 1st hilbert call
right(-angle)
forward(size)
left(-angle)
forward(size)
left(-angle)
forward(size)
right(-angle)

# Continue from first call of hilbert
forward(size)
left(angle)

# 2nd hilbert call
right(angle)
forward(size)
left(angle)
forward(size)
left(angle)
forward(size)
right(angle)

# Continue from second call of hilbert
forward(size)

# 3rd hilbert call
right(angle)
forward(size)
left(angle)
forward(size)
left(angle)
forward(size)
right(angle)

# Continue from third call of hilbert
left(angle)
forward(size)

# 4th call of hilbert
right(-angle)
forward(size)
left(-angle)
forward(size)
left(-angle)
forward(size)
right(-angle)

# Continue from fourth call of hilbert
right(angle)

Eureka!

Answer 3

As @Tom Zych and others mentioned, this is a problem called recursion that can be hard to wrap your mind around at first (sometimes requires thinking about problems in a totally different way than usual).

The most classic and easily understood (but not necessarily useful or powerful) example of recursion is the factorial generator. Given a positive integer n, the factorial of n is equal to the product of all the positive integers less than or equal to n. We write the factorial of n as n!:

n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1

Now with recursion we want to see, "what is the pattern here that repeats and gets simpler as I try to solve the larger problem?" Let's try 5! for instance:

5! = 5 * 4 * 3 * 2 * 1

What is the first thing we do when solving this equation? We take 5 and multiply it by something. This is perfect, because if we had a factorial function fact(n), we would probably take n as its parameter:

def fact(n):
    return n * #something

All that remains is to figure out what that #something is. But we just wrote it above:

5! = 5 * (4 * 3 * 2 * 1)

But how is out new #something just a smaller problem that is essentially identical to our original problem? Watch, this is the magic of recursion:

5! = 5 * 4 * 3 * 2 * 1
   = 5 * 4!
4! = 4 * 3 * 2 * 1
   = 4 * 3!
3! = 3 * 2 * 1
   = 3 * 2!
2! = 2 * 1
   = 2 * 1!
1! = ???

As you can see, for most any given n,

n! = n * (n-1)!

We're almost there, now that we've discovered our pattern, we need to worry about the exception case, the simplest case, (when n = 1, there's nothing else to multiply by). In recursion, we call this the base case, and fortunately we know exactly what to do in this base case: 1! = 1. So in summarizing our logic, we can write our recursive factorial function:

def fact(n):
    # Take care of the base case first
    if n == 1:
        return 1
    # Then break down the larger case into its recursive sub-problems
    else:
        return n * fact(n-1)

Your Hilburtle program is a tad bit more intricate, but if you know some of what Hilbert curve analysis is about, and you're beginning to understand recursive program logic, you should be able to figure out how it works. Good luck!

Answer 4

This is referred to as recursion. A recursive function usually solves a small problem but also has the ability to break larger problems into smaller ones that it can more easily solve.

In your example, it looks like the program may be some path-exhausting program.

Answer 5

When level equals 0, hilbert(level,angle) just returns, that is, does nothing.

Now consider what happens when level equals 1: Calling hilbert(1,angle) executes these statements:

turtle.color("Blue")
turtle.speed("Fastest")
right(angle)
forward(size)
left(angle)
forward(size)
left(angle)
forward(size)
right(angle)

It looks to me that this probably draws three sides of a square.

The hilbert(level-1,...) statements have been removed since level-1 equals 0 and we already determined that hilbert(0,...) does nothing.

Now, consider what happens when you call hilbert(1,-angle). Next, think about what happens when level equals 2. I hope this gives you an idea of how to proceed.

PS. Lovely thing about Python -- you can run programs interactively to visualize what calling hilbert(1,angle) does, then hilbert(2,angle) does, etc...

Answer 6

This is a powerful programming technique called recursion, where a problem is solved by breaking it down into similar but smaller problems, until you reach a point where the problem is small enough to solve easily.