Okay. We want to examine yet another recursive function. Again, we're going to show how that recurse function can be written iteratively. We're going to show in this particular example, which is the Fibonacci sequence, its very famous. That sequence is defined as the nth element of the sequence is equal to nth minus one element of the sequence plus the nth minus two elements of the sequence, where the sequence initially starts with the zeroth element being zero and the first element being one. So if you follow this formula, f of 2 would be 0 plus 1, namely 1, and f of 3 would be 1 plus one, which would be 2, and f of 4 would be 1 plus 2, which would be 3 and so on. What's interesting is, even though the numbers at the beginning look very small, the sequence grows exponentially. So here's a definition. Doing it iteratively. I'm going to use longs because if I want, I can easily write something that exceeds a single-precision integer. So I'll start off with f2 equals 0 and f for 1 equal 1. Here's where I add them together, f2 plus f1 becomes a new f2. We retain the older value of the sequence in this step. Then after we make this summation, f1 becomes cf older value. You can go to c and check that that will indeed compute this sequence. We turn for n, we have to compute it up until the nth element of the sequence, and then we return f2. So that's an iteration. But if you think about it, the sequences and more naturally defined with a recursion. Here's the recursion. If n is less than or equal to 1, then return n. That means if n is 1, then f of 1 the Fibonacci sequence at 1 is 1. Or if it was 0, the Fibonacci sequence of 0 is 0. For our purposes, the Fibonacci sequence is only defined on the non-negative integers. Else, return the recursive call of Fibonacci n minus 1 plus a recursive call of Fibonacci n minus 2. So that's where we have a recursion. Indeed, both recursions countdown. So in each call to this recursive function, we get two calls and so on. So notice, if you have to go very deep in computing Fibonacci of n, you are going to get something like to the nth calls of this sequence in order to do the number of summations that you'll need when you get to a large value of Fibonacci using the recursive formula. Here I'm just going to ask you to print a table. We're going to print a table with ordinary Fibonacci and recursive Fibonacci. Okay. We are going to exit that routine. Now I'm going to execute it. I'm going to do a small value of n just to show us what it is. So iterative Fibonacci, recursive Fibonacci answers 0, 0, 1, 1, 2 , 1, 1. The third member of the sequence is 2, forth member 2 plus 1 is 3, 3 plus 2 is 5, 5 plus 3 is 8 and so on. Works very quickly. Let's do it again though. Let's do it for up to 25. We'd zip by on our screen a whole bunch of values. Then we can see that 15 is 610 plus 987. So we get 1597, indeed both the iterative and recursive give us the same answers as expected. But now, let's look at a much larger number. Let's look at 45. Now look what happens. We've hit 40, the screen is slowing down, I'm working on a fairly modern Mackintosh. All the answers are jiving. You can add the irrespective previous two to get this but, okay. That wasn't large enough, I'm going to do it once again because it started to slow down, but what if do 50? Now, you see at 43, all of a sudden the screen is frozen. We saw that it did 44 and that took a significant number of seconds. Now look 45, it's still crunchy. Crunch, crunch, crunch. Now, finished. But you can see and notice full lengthening of time. I'm not going to let this run any further. I just want you to think about that. I'm going to abort this. So what is going on is, on the recursive side and if I had separated and you can do this yourself at home. You could separate writing it iteratively from writing a recursively and you could see you would readily get 45, 46, 50 until you get a number too big for the accuracy of long integer. But it would run very quickly because it's a simple iteration and its just a linear time set of additions in that sequence. On the other hand, calling it recursively means that, we're going to ultimately end up with a bunch of ones being added. Maybe a bunch of zeros, and those, for example, here we're going to have something like 4,000,000. So this is 4,000,000. So this is over a billion. When you have over a billion function calls, you have a whole bunch of operations going on on what on the stack and on calling a function, which is one of the more complex functions at the machine level, that can actually take some few, maybe tenths of a millisecond but still some significant time in relation to the simple calculation you're doing. So that's a pitfall. If you use recursion, it could lead to a significant slower. Even though on the surface, it gives you a more logical easier to understand program for recursive functions such as human aging.
