This chapter has just three sections:
Sequences. You've all seen them. Someone on the internet gives you something like the following and asks, "What is the next value"?
Each of these are sequences of numbers. But, more importantly, there are functions which produced this order, functions at least partly based on their index in the list.
For example, the second sequence happens to be an ordered list of numbers produced for the factorial function is in
The first of those sequences is formed by adding the index to the preceding value in the sequence as in
The last happens to be called the Fibonacci Sequence produced by starting the sequence off with 0 (F_{0}) then 1 (F_{1}), and following those with
It's partly a function, so name your function, your choice. It's partly a function of the index, so choose the means of generating the index. Let's have an arbitrary set of functions create an arbitary set of sequences. The column header describes the function and the rows under each is the sequence.
So, let's dig down a bit further to get our head around what is really happening here. Again, keep in mind that, even though these are repeated calls to the same function, they are in reality different calls, because of a notion called a Stack Frame. Every call of the function factorial, results in memory being carved out – a Stack Frame – to hold at least the variable N. As you do each call, a new N is recorded there, at first N=4, and then N=3, and then N=2, finally the N=1, at which point the returns start executing, unrolling ourselves in the stack, each return returning a new value to its caller. In the following, remember that the value being returned is each stack frame's N multiplied by the value returned from the preceding call. Recursion.They are all just sequences. It's up to you and your needs.
Of course, you can program a routine supporting any of those functions. To get any of those values, throw your index value N at the function, and the function will kick back the value in the sequence. To create these lists, these sequences, just loop, each iteration generating the index values, calling your function.
The likes of the Fibonacci Sequence and that of factorial add an interesting quirk. There certainly is an aspect of a function and of an index passed to that function, but their values at that index are dependent on preceding uses of that same function for preceding indexes.
Sure, a program can be written as an explicit loop, each iteration calling a function, but the values passed to it is from some preceding call to that function. That's straight forward enough. Another way, though, is to create a function that takes into account that the earlier values actually did come from itself. And that's where the notion of Recursion comes from as we will be seeing shortly below.
Although not strictly a computer science subject, Induction is one of those concepts that anyone in mathematics ought to know. The beauty of Induction is in its ability to aid in proving some mathematical concept. Even so, because of the limits inherent in computer science, induction has a way of breaking down. As you are going to see, this has a direct relationship to sequences.
So, Induction. Suppose that you want to prove, for whatever reason, that
You could simply program a graph each of these as in
and see from inspection in the graph that these statements are always true.
But, using Proof by Induction, there is another way. The essence of it is
So, from our two examples, the question in the first is
So, we choose arbitrarily an x = 3.
Next step. We get to assume that when our x = k, the statement is true. We just assume that. We then, using that assumption, ask whether it is true for x = k + 1.
So, we get to assume that the following is true:
Notice, again, that for k = 3, we learned that this k is true.
So, is that statement true for x = k + 1? Said differently, using our assumption, is
A little bit of algebra later:
From even step 2 there and simply because k must be positive and because
we see that our statement under test is clearly true. But, we also see that, since it is true that for x > 2,
we also see from step 3 above that it is true that
Let's run this again, this time to prove that
Again, let's choose our specific case to be x = 3.
For this specific case, is 2^{3} > 3 + 1 ? Yes, clearly.
So, on to the next step, we get to assume that
Recalling that we are trying to prove
we go on and want to prove that for an x = k+1 it is true that
again, having made the assumption above.
With some algebra, first we know that
where the stuff in red in the last step was our base assumption from above. And, by induction, we just then proved that
Now, speaking philosophically, notice again that induction assumes that we can just keep adding one, ultimately out to infinity. We said that if k works, all we need to do is prove that k+1 works. That is great in theoretical math, but not so much in the more real world of pragmatic computer science. What, after all, is an integer in computer science, or more to the point an integer in your programming languages. Typically, an integer is 32 bits in size. That is all. So, if we add 1 to the most positive integer, is the result one greater? No, it wraps back to being the most negative representable integer. More specifically, adding one to
which happens to represent a negative number when those 32 bits are treated as a signed binary integer.
In short, mathematics allows for an infinity, integers in computer science do not. Proofs like this work well within the range of such numbers, just not past it.
Let's look at the function Factorial, specifically 4!.
But isn’t that also
We can call a factorial function to find 4!. Just pass in the 4 to factorial and have it do its stuff. So, certainly, we need to know the 4 but the factorial function will need 3!. No problem, it just calls to find 3!, calling factorial and passing in one less than the four, 3. And that same factorial function, being passed the 3, knows that it wants 2!, so calls again, this time asking for the 2!. Each new call of factorial is going to return its value,
and done, returning 24 to the initial caller. That is the essence of recursion. A function keeps calling itself, iterating until it knows a default value (i.e., 1! = 1) and stops calling and starts returning results.
Or, as another way of looking at it,We needed to have gotten to a place where the function knew exactly what to do. 1! = 1, at which point it can return the value of 1 to the caller and stop calling!
It sort of looks like a loop, but programmatically there isn't a loop to be found here. The function just keeps calling itself. Here, the factorial function is calling itself, just once, but the effect is repeated calls. Those repeated calls ended when the input parameter is 1 at which point it completes the function and returns the value for that one call. And the completion returns a value to the preceding caller and that to the preceding and so on, until the very first call is reached.
So, in Java say, what does such a factorial function look like?
That is all. Notice, in particular, that each new call has a different input parameter, here one less each time. In effect, keep calling the function with ever decreasing versions of N until we reach the value 1, in which case, first return the value 1, and then, repeatedly, N multiplied by the returned value(s). The initial call to calculate our 4! Would simply be
So, let's dig down a bit further to get our head around what is really happening here. Why is this working, and how can we know who the caller in each step as we return?
Keep in mind that, even though these are repeated calls to the same function, they are in reality different calls. This is because of a notion of something called a Stack Frame. Every call of the function factorial, results in memory being carved out – a Stack Frame – to hold at least the variable N. As you do each call, a new N is recorded there, at first N=4, and then a new N=3, and then a new N=2, finally the N=1, at which point the returns start executing, unrolling ourselves in the stack, each return returning a new value to its caller. In the following, remember that the value being returned is each stack frame's N multiplied by the value returned from the preceding call. Recursion.
In the following figure of stack frames, with each call we are working out way down the stack, and then returning our way up the stack.
This same factorial operation could have been done in a simply loop as well. This was just to show you the capability of recursive calls, calls to the same function. As a word of warning, be careful with using this if the number of calls is particularly large and the function is using many local variables or a lot of such calls to complete. Each call results in some memory being allocated for such a purpose. With a lot of calls, there is a lot of stack memory being allocated as well, and you can run out.