Today we're going to carry on the recursion story a little more. Many of
you, I hope, have seen my initial effort in this direction which is the Recursion
video. It's featured stack frames - how recursion is actually done - and the
answer delivered back by 'factorial' will be an integer answer. So, I thought what
we'd do today is move on to another example much beloved of Brady [Haran].
It's called the Fibonacci sequence. He was an Italian gentleman - that's not his real
name that was the nickname he was given - I'll try and stick to mathematical notation
here the n+1 Fibonacci number is defined to be the
nth Fibonacci number plus the n - 1th Fibonacci number. Whereas with
factorial it just followed itself recursively round one strand a recursion
here you're adding in a second strand of recursion. So this is sometimes called
Multiply Recursive, whereas 'factorial' will be called Singly Recursive. But like
all recursive definitions of functions you do need an escape route at the
bottom. If you keep on calling yourself you could go on to infinity. But as you
can see here, everything's fine so long as you write down what the first
Fibonacci number is and the second one. The second Fibonacci number and the
first Fibonacci number are both defined to be 1, We can now write down the
Fibonacci sequence because it starts off with a 1 for the first number, a 1 for
the second number. So if I want F(3) then I'm got to make n be 2 there. 2 + 1
is 3. So Fibonacci of 3 [F(3)]is the same as Fibonacci of 2 [F(2)] plus Fibonacci of 1 [F(1),]
Both [are] 1. So, the answer for F(3) is 2. Every Fibonacci number is the sum of the
two that immediately precede it. So the next one, then, is going to be 2 + 1 [i.e.] 3.
The one after that 3 + 2 5, 8, 13, 21. You might think: "Well, very
interesting but what does that apply to? Why should that be so fascinating?"
Well, it's fascinating first of all, for the simple reason that in the Computerphile /
Numberphile family, some of you will know that the wonderful 'Godfather' Brady
has already made and got ahead of the game, a video about Fibonacci. He actually
had a Fibonacci Tartan designed and had it made up! [video insert] >> Brady: ... and the rows and the threads
that have been used to create this design are based on the Fibonacci sequence.
>> DFB: Heaven knows how much it cost him to get it made up! But there it is. >> Sean: As computer
scientists why do we care about Fibonacci?! >> DFB: The reason I'm doing this with
you is the following: Like 'factorial', 'Fibonacci' is a recursive
function that can be de-recursed. You could do it in 'for' loops - things that can
be de-recursed are called Primitive Recursive, so Fibonacci is just another
one. It enables us also to draw pretty pictures, which we'll do in a minute and
I rather like doing that. But having done Fibonacci and factorial - but this will have to
be in a separate video - you then want to say: "Well, not everything can have the
recursion taken out of it. Some things really are recursive. I've actually
written a PostScript program that will print out the Fibonacci numbers for you
up to the value of 'fib(10)' being 55. We'll put out a link to this program and those
of you who've got Ghostview, or Ghostscript set up, try running it. You should
get this coming out all right. I can only apologize it I've done it in
Helvetica. The thing you've got to be prepared for in PostScript is you're at
the mercy of the fonts you have available in your interpreter. Don't
blame me if it comes out in boring Courier. That tends to be the default
when it doesn't have access to the font that's asked for. >> Sean: Comic Sans!
>> DFB: It's more likeely to be Courier actually! When you look inside the program for that and
I will do, very briefly, but absolutely not in detail ... First of all, here is my
definition of Fibonacci '/fib' is going to end 'def'. That's the
definition of the Fibonacci function. To head off trouble at the pass I've even
put error messages in it. What I made it do, to get those numbers to come out, is
go round a 'for' loop ten times and every time it goes around it calls up 'fib' but
every time it goes into 'fib' it calls itself recursively. It gets straight back
inside itself and, there we are, out it comes. It does work absolutely fine but
if you're going to start doing recursive stuff in PostScript then, by definition,
you've got to have something that corresponds to stack frames, right? And we
now have C and Java and things to do it; they do it automatically. What about in
PostScript? Well, PostScript is wonderful it makes
you make your own stack frames but it gives you a fabulously - what's the word -
versatile, way of doing it. Basically in the second line here this thing '10 dict begin'
and what that means is: "Get me a dictionary with ten spaces in it". And if
you think that that '10 dict' is [also] like saying: "Give me a stack frame with 10
spaces in it because I'm going to use it and put values in it - to manipulate them
all on my own". You'll remember when you look back at the stack frame story in
the Recursion video. It's great C does it for you.
But the penalty, if you like, is you've got to accept the way it handles the
stack frame. unless you want to get into some most appalling hacking you'd better
not mess with your stack frames. You could end up in an awful mess. Whereas
PostScript is basically doing its usual thing. Y'know: "You're a serious program with
tons of experience. If you get messed up you'll soon sort yourself out I'll let
you manipulate the stack frame every time we go around recursively into 'fib' "
It basically hits '10 dict begin' which says: "Make me another stack frame". I mean
another recursive instance of Fibonacci.W what other things can we do with
Fibonacci that make it interesting for mathematicians as well as computer
scientists? Well, one of the things that I set many years ago,
in a Digital Documents course, was the following. If you put Fibonacci-sized
boxes together and group them properly and then you join them up you can draw
some most amazing shapes. This is the Fibonacci spiral and if you look here
you can see what I'm doing. Once I've got the basic Fibonacci recursive function
working I've built on top of it extra routines. And this is the beauty of
PostScript. You not only get the stack, you get the recursion, you get the
stack frames ... but you can draw two dimensional pictures as well! So, what I
got it to do was to go round and every time it visited 'fib' and got an answer
like 1 [interpret this as]: "draw a box of unit size". And then the next box along, just to its left, is
also of side 1. And of course the secret is knowing where to attach the
next box. I have attached the square of side 2 direct to the south,as it were,
of the two boxes of side 1 and then the 3 box gets attached to the east
side. And then it goes up north and then it goes west. And as you go around you
get 1, 1, 2, 3 When you've stacked your boxes correctly you go into
them and you draw an arc across each of the boxes and I've chosen to do it, at
this time, in an anti-clockwise direction And you end up with this beautiful
looking spiral - known as the Fibonacci spiral. It's an approximation to a
well-known mathematical object called the logarithmic spiral