## A magazine where the digital world meets the real world.

# On the web

- Home
- Browse by date
- Browse by topic
- Enter the maze
- Follow our blog
- Follow us on Twitter
- Resources for teachers
- Subscribe

# In print

# What is cs4fn?

- About us
- Contact us
- Partners
- Privacy and cookies
- Copyright and contributions
- Links to other fun sites
- Complete our questionnaire, give us feedback

# Search:

# She Loves Me...She Loves Me Not

Fibonacci numbers crop up in nature lots - count the number of petals on a flower "She loves, me. She loves, me not, She loves me, ..." Whether she loves you or not, the chances are the count of petals was a Fibonacci number (Daisies usually have 34, 55 or 89 petals, for example - all Fibonacci numbers). What are the Fibonacci numbers: 1,2,3,5,8,13,21,... Can you spot the pattern? Just add the previous two numbers to get the next.

The sequence crops up in bees too, because of the way male and female bees breed - a fact that is used in the book "The Da Vinci code". Unfortunately author Dan Brown got the reason wrong as computer scientist, Harold Thimbleby of Swansea has pointed out.

Computer Scientists like the Fibonacci sequence because it is a good example of something that can be programmed easily using what is known as recursion. Recursion just means you define something using a simpler version of itself: If we write the 5th Fibonacci number (which is 8) as fib(5), the 4th (which is 5) as fib(4) and so on then we can calculate it as:

Define fib(5) = fib(3) + fib(4)

That tells a computer to calculate fib(5) by calculating fib(3) and fib(4) first, both simpler Fibonacci calculations, and then add them together. fib(4) and fib(3) are worked out in the same way using simpler calculations again. We can write this to work for any number (let's call it n) as:

Define fib(n) = fib(n-2) + fib(n-1) if n > 1

That just says that for any number n that is bigger than 1, work out the nth Fibonacci number by first working out the previous two, fib(n-2) and fib(n-1), and adding them. We then just have to say how to do the simple cases you eventually end up at, when n is either 1 or 0:

Define fib(n) = fib(n-2) + fib(n-1) if n > 1

| fib(1) = 1

| fib(0) = 1

You can write your own recursive programs that draw pictures based on recursive patterns. In fact the man-woman picture here is drawn by a program using a Fibonacci recursion program almost identical to our definition. It just uses instructions to draw men or women instead of adding numbers. As it turns out the picture shows the family tree of bees too. The mathematical computation creating the picture mirrors the natural process.

Each row of the man-woman picture contains a fibonacci number of people in it and is defined almost identically to the fibonacci recursion.

Define fib(n) = fib(n-2) BESIDE fib(n-1) if n > 1

| fib(1) = woman

| fib(0) = man

The difference is instead of stopping at numbers we call programs (defined elsewhere) that draw a man or a woman. Then instead of adding we use the command "BESIDE" to say place the figures side by side. This means that in the drawing version of program fib, fib(5) draws 8 figures.

We can layout the different rows on top of one another in a similar way. Draw the fib(n) row, then do the same again on the result of computing a picture with one less row. Here we use ABOVE to put the two parts of the picture on top of one another rather than side by side. Draw the whole thing with (say) 8 rows with the command fibsequence (8)

define fibsequence(n) = fib(n) ABOVE fibsequence(n-1) when n>0 | fibsequence(0) = fib(0)

fibsequence (8)

The above are programs for a programming system called Geomlab by Mike Spivey of Oxford University. The only difference is that in Geomlab you would write the single characters & for the command ABOVE and $ for BESIDE. Download the free Geomlab package and you can run the program to generate the picture, and then play about with it to create your own variations.