## Saturday, May 24, 2014

### Day 29 of 30: Recursive Functions

This is Day 29 of my 30-day blogging challenge. I can see the checkered flag in the distance.

Common Core Algebra seems more concerned about functions and families of functions than the previous Integrated Algebra in New York State was. It used to be that it was all linear equations and if you saw f(x), you just think "y". They had their uses, but we didn't get to talk much about them -- there was already too much to talk about in that course, and we had a hard time making all of it happen.

Well, Common Core is no different. They just give you a different "all that" to cover, and they really do want you to cover it all. When it comes to functions, they not only want the standard linear, quadratic, exponential and absolute function, but also cubic, square root, piecewise and recursive. Some of them need to be graphed, some only have to be used for evaluating, for example, f(3) or f(-5).

I can get to piecewise another time. My students are getting the hang of them. Well, some of them are. Some of the time. Okay, so maybe not. And I don't blame them. I didn't have to deal with those until later on.

Recursive functions, on the other hand, I don't remember from math class at all. Seriously. I remember them from computer programming. This isn't to say that I hadn't seen them in a math class first before I programmed a recursive function, but I know what left its mark on my memory and where it took.

A recursive function is one that calls itself. It uses itself in its own definition. The two most obvious examples (and Common Core won't use obvious examples are:

Factorial: f(n) = f(n - 1) * n, f(1) = 1

Triangular Numbers: t(n) = t(n - 1) + n, t(1) = 1

To calculate f(n) when n = 5, you do the following: f(5) = f(5-1) * 5 = f(4) * 5. But you need to know what f(4) is.
Well, that's easy. f(4) = f(4-1) * 4 = f(3) * 4. Okay, so now we need to know f(3) ... and then f(2) ... and so on down to f(1), which we are given.
As I told me students: you might as well start with f(2) and work your way up. We'll have to do all that work anyway. Then find f(3), f(4) and so on. If you are programming a computer ... well, I'd probably do it the same way for simple things, but use a recursive function when the professor tells me to do so. Most of the recursive things I've ever coded worked fine with a For...Next or Do...End loop.

Likewise, t(5) would work the same way. The only difference is that I used the letter t for triangular because I already used f for factorial in the same example. Be careful! Students can actually get confused by this. (I'm not kidding.)

Real-World Connection: Forgetting about where factorials and triangular numbers may occur in your everyday existence, recursive functions are part of the real world. Take the function clean(n). Suppose you wish to evaluate this function for the value of n = floor. There's a problem with this because your wife may tell you that you can't clean the floor until you evaluate clean(counters). And you can't do that until you evaluate clean(cabinets).

Now keep in mind that this is just supposed to be an illustration of a recursive function. However, it isn't exactly a true parallel example. For one thing, one you can't calculate 5! (5 factorial) without first calculating 4! (4 factorial). On the other hand, you can clean the floor without cleaning the counters or the cabinets. However, in both cases, according to my wife, at least, you'd be incorrect.