Chapter 7: Sequences, Induction, and Recursion

This chapter has just three sections:

1. Sequences
2. Induction
3. Recursion

Sequences

Sequences. You've all seen them. Someone on the internet gives you something like the following and asks, "What is the next value"?

1. 1, 3, 6, 10, 15, 21, _ (28, Add one-based index into sequence to value at preceding index.)
2. 1, 2, 6, 24, 120, 720, _ (5040, One-based index factorial.)
3. 0, 1, 1, 2, 3, 5, 8, 13, _ (21, Fibonacci Sequence)

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

1. 1! = 1
2. 2! = 2 * 1 = 2
3. 3! = 3 * 2 * 1 = 6
4. 4! = 4 * 3 * 2 * 1 = 24
5. 5! = 5 * 4 * 3 * 2 * 1 = 120
6. 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
7. 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040

The first of those sequences is formed by adding the index to the preceding value in the sequence as in

1. 1
2. 3 = 2 + 1
3. 6 = 3 + 3
4. 10 = 4 + 6
5. 15 = 5 + 10
6. 21 = 6 + 15
7. 28 = 7 + 21

The last happens to be called the Fibonacci Sequence produced by starting the sequence off with 0 (F₀) then 1 (F₁), and following those with

F_N = F_N-1 + F_N-2

1. 0 (Initial 0)
2. 1 (Initial 1)
3. 1 = F₂ + F₁
4. 2 = F₃ + F₂
5. 3 = F₄ + F₃
6. 5 = F_{5 + F4}
7. 8 = F₆ + F₅
8. 13 = F₇ + F₆
9. 21 = F₈ + F₇

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.

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.

• Fibonaci : F_N = F_N-1 + F_N-2
  The function produces F_N by having F_N-1 and F_N-2 passed into it.
• Factorial : F_N = N * F_N-1 = N * (N-1) * (N-2) * … * 1
  The function produces F_N by having F_N-1 and N passed into it.

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.

Induction

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

x² > x + 1, for all integers x greater than 2.
or
2^x > x + 1, for all x greater than 1.

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

1. Prove that it is true for one value x,
2. Assuming that it is true for some x = k, prove it is true for an k + 1.
3. Proof complete.

So, from our two examples, the question in the first is

Is x² > x + 1, for all integers x greater than 2?

So, we choose arbitrarily an x = 3.

Is 3² > 3 + 1? Yes. So far so good.

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:

k² > k + 1

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

(k+1)² > (k+1) + 1 ?
Remember, we are trying to prove that x² > x + 1 and we get to assume that k² > k + 1. (We are not yet complete.)

A little bit of algebra later:

1. Is k² + 2k + 1 > k + 2 ?
2. Is k(k + 2) > k + 1 ?
3. Is k² + 2k > k + 1 ?

From even step 2 there and simply because k must be positive and because

k + 2 > k + 1

we see that our statement under test is clearly true. But, we also see that, since it is true that for x > 2,

k² > k + 1

we also see from step 3 above that it is true that

k² + 2k > k + 1

Let's run this again, this time to prove that

2^x > x + 1, for all x greater than 1.

Again, let's choose our specific case to be x = 3.

For this specific case, is 2³ > 3 + 1 ? Yes, clearly.

So, on to the next step, we get to assume that

2^k > k + 1

Recalling that we are trying to prove

2^x > x + 1

we go on and want to prove that for an x = k+1 it is true that

2^k+1 > (k + 1) + 1

again, having made the assumption above.

With some algebra, first we know that

1. 2^k+1 = 2 * 2^k
   
   Since we get to assume that 2^k > k + 1 we get
2. 2^k+1 = 2 * 2^k > 2 * (k + 1)
3. 2^k+1 > (k + 1) + (k + 1)
   And for all positive k, the following inequality is still true
4. 2^k+1 > (k + 1) + 1
5. 2 * 2^k > (k + 1) + 1 when k > 1.

where the stuff in red in the last step was our base assumption from above. And, by induction, we just then proved that

2^x > x + 1, for all x greater than 1.

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

0111 1111 1111 1111 1111 1111

1000 0000 0000 0000 0000 0000

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.

Recursion

Let's look at the function Factorial, specifically 4!.

4! = 4 * 3 * 2 * 1

But isn’t that also

4! = 4 * 3!
where
3! = 3 * 2!
and
2! = 2 * 1!

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,

1. 2! returning 2 * 1 = 2
2. 3! returning 3 * 2 = 6
3. 4! returning 4 * 6 = 24

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.

4! = 4 * 3! So, what is 3! Call factorial for 3.
3! = 3 * 2! So, what is 2! Call factorial for 2.
2! = 2 * 1! So, what is 1! 1! is by definition 1 so stop calling.
2! = 2 * 1 = 2 Return 2.
3! = 3 * 2 = 6 Return 6.
4! = 4 * 6 = 24 Return 24 to first caller.

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

long factorial_result = factorial( 4 );

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.