3.1.2
3.1.2
What is a recursive function
Introduction
We are going to go over a lot of the fundamentals your going to need to know from here on out. Specifically this article has been geared to prepare readers for Chapter 3.2, in which we begin with the "elementary recursive functions". There is of coarse a lot of information out there on the internet on this subject already, but it can be a little intimidating to a new comer. The purpose of this article is therefore to explain all the concepts in a simple and understandable manner that doesn't require you to be a mathematics major. Far from being incomprehensible, recursive functions are actually pretty simple and intuitive conceptually. There are recursive concepts in art, for example the Escher work used at the top of this page. Recursive thoughts also seem to occur in the human mind naturally. For example, have you ever considered the train of thought: I think, you think I think, I think you think I think, etc. If so, then you already have an intuitive understanding of recursive concepts!
What is a Function?
You may have heard of the concept of a "function" from High school or college. Before we can learn what "recursive functions" are we first need to get an idea of what a function is. As a math tutor I have first hand experience of how the concept of a function can be tricky for people who are just learning about it. The first thing you need to know is that it is in many ways functions are a natural extension of concepts begun in algebra.
One of the most fundamental concepts in mathematics is of coarse "number". It's so fundamental in fact, that it is among some of the very first mathematical concepts we learn as children along with shapes and colors. Even the concept of number is already an impressive abstraction. A Number doesn't refer to a physical object, or even a physical collection, but rather the "number" of object's in a physical collection (whatever that means!). You won't find "3" anywhere in the real world, but you can find "3 somethings". What a number is ultimately is an abstraction of quantity without respect to "quality". That is, we say a collection of 3 rabbits, and a collection of 3 ducks, has the same number of elements, even though they are not the same collections.
For elementary purposes the "Counting Numbers" are sufficient, and this is more or less what I usually mean by number. However, "number", in this sense is really only the beginning of the abstraction process. Just as "number" is an abstraction of a "collections size", we can now consider the further abstraction of performing "operations" with numbers. For example we can think of combining the elements of two collections into a single collection, as "adding". Rather than talk solely about 1,2,3 etc. we can now speak of such things as 1+1, 2+2, 2+3, etc. It is important to understand that these "arithmetic expressions" are also, in a sense, numbers! 1+1 is just another way to write 2, 2+2 another to write 4, and 2+3 another to write 5. The abstraction continues ... next we can take away elements from collections, and this is the basis of subtraction. One can then form new operations upon old ones. Multiplication is based on repeated addition, and division is the inverse of multiplication. Exponents are a shorthand for repeated multiplication, and square roots and logarithms are the two inverses of exponentiation. All of this forms the backbone of "arithmetic", which is really just an abstract set of relationships between numbers. Most everyone understands mathematics up to this point. The difficulty usually begins at the point at which "letters get introduced into math".
The "letters" are of coarse the "variables" of "algebra". Algebra is really just a further abstraction upon arithmetic. Think of it this way: if you understand arithmetic, then you already have the foundation to understand algebra.
A "variable" is really just a further abstraction of number. A variable is usually denoted by some letter or non-numeric symbol. For example we might use "N" to represent "a counting number". The important thing about N is that it is not a specific counting number, but rather "could be any counting number". There are two ways to view variables actually. We can think of a variable as a kind of "black box". There is a number in the black box, but we don't know what it is. We might be told what "kind of number" it is, but we have no idea what it's specific value is. The other way to think about a variable is that, it literally varies from one value to another constantly, or that it literally is all values at once. The difference is really about how we want to use the variable. Most people are familiar with variables as the unknowns in an algebra problem. For example:
2N+5 = 19
In this case, a "variable" is really just an abstraction of arithmetic. Basically the question is: what number multiplied by 2 plus 5 equals 19? Even though "N" is an unknown, we have specified a known property of it: that twice it's value plus 5 equals 19. We can try to guess the value of N. For example, try 1:
2(1)+5 = 7
This proves that N does not equal 1. Does it equal 2:
2(2)+5 = 9
No. We could continue to guess, but a better way is to understand something about algebraic manipulations. For example, if 2N+5 = 19, then it follows that 2N must be 5 less than 19, right? 2N must be 14, because then 2N+5 is really 14+5 which is 19. So we can say that:
2N+5 = 19
implies that...
2N = 14
What number doubled is 14? You might recall that 2x7 = 14, so we can say N=7. We have "solved" for the unknown, because we knew something about it. The significance of this is basically that we can deduce new unknown information from a set of known facts. That is actually the heart of mathematics itself! It is a manifest property of the world because it is structured in some way. Think of mathematics as a "reasoning approach" to finding new information from old information, instead of some arcane set of magic rituals. My most general definition of mathematics is a "specific and structured mode of thought". Mathematics then becomes not about what is "right" and "wrong", but rather what is "effective" and "ineffective".
Now there is another way to view variables that is equally important, and in fact is even more important in the field of large numbers. A variable can be used to define a property for an infinite number of members. For example, is b,n and m are counting numbers then we can say that:
bnxbm = bn+m
There is nothing to "solve" here. Rather, it is a statement about ALL counting numbers. They MUST follow this identity. In this case the variables are really sets, and the statement a relation between them.
So this is all a variable really is: a placeholder for a number: a proxy, a substitute. The advantage is that it allows us to reach another level of abstraction beyond numbers. Just as numbers are an abstraction of relations between collections, variable expressions are an abstraction of relations between numbers! Think about that for a moment: what would the next logical progression be? Hmm...
Well why not take this one step further and talk about relations between variables! THAT is what a function is! Ultimately, since variables are just numbers, a function is really just a relation between numbers. This relation can be entirely contrived, or it can be based in a complex mathematical relation. Before we get ahead of ourselves, let's establish some notation for this new concept of a "function".
We first begin by having an equation with at least two variables. For example:
y = 3x+4
In this case, "y" is a variable whose value is related to the value of "x". Specifically "y" is always equal to three times "x" plus 4. We can also say that "y" is a function of x. Variables in this case, aren't unknowns, but rather can take on any value. However, for every value of x there is a corresponding value of y. Here are some specific examples to ground the concept:
if x = 1
then y = 3(1)+4 = 3+4 =7
if x = 2
then y = 3(2)+4 = 6+4 = 10
if x = 3
then y = 3(3)+4 = 9+4 = 13
etc.
A function is basically a mathematical operation. It takes an input value, in this case x, and then produces an output value, in this case y. Thought of in this way, a function is no different than an arithmetic operation, like adding or multiplying. Here is an example of an operation which is really just a function. You may recall that the factorial of N is defined as multiplying together every counting number from 1 to N:
N! = (1)(2)(3) ... (N-1)(N)
Now we can say that N is an input, and N! is the output. For example:
if N = 1
then N! = 1! = 1 = 1
if N = 2
then N! = 2! = (1)(2) = 2
if N = 3
then N! = 3! = (1)(2)(3) = (2)(3) = 6
etc.
So the distinction between an "operation" and a "function" is somewhat arbitrary. For our purposes, they are one and the same! So if you understand the factorial, then you basically understand the structure of a function. So far so good right? At this point it is customary to introduce functional notation. We can say that:
f(x) = y
It is usually at around this point that people get confused. First and for most, f(x) is not "f" multiplied by "x". The notation is actually composed of two parts. The first part "f( )" is considered the "function", and the second part "x" is imbedded inside of it as the input of the function. Just as 3! can be computed, we can think of f(3) as a special operation on 3 that can be evaluated. We can also think of f(x) as just another way to write "y". The advantage of using f(x) instead of y, is that we can now specify what value is going "into y". Let's say that:
f(x) = 3x+4
We can then say that:
f(1) = 3(1)+4 = 3+4 = 7
f(2) = 3(2)+4 = 6+4 = 10
f(3) = 3(3)+4 = 9+4 = 13
etc.
Note that, unlike y=3x+4, we didn't have to specify x=1,2,3,etc. in advance. The value is announced within the functional notation. Also, while "y" really represents all possible outputs of the function, f(1), f(2), f(3), each represent a distinct output (value). The functional notation will form the basis of our search for larger and larger numbers from here on out.
One important note: f(x) can be recycled to represent ANY function. In a sense, f(x) is a "variable" of "variable relations", representing any function possible. Just as the "x" in one algebra problem is not the same "x" in another, the "f(x)" in one place, is not necessarily the same as in another. However, at any point we can assign a specific function to f(x).
There are a few ways to conceptualize what a function is. We can treat a function as another kind of "black box", only this time it doesn't simply contain a number, but it is a kind of "computer". You can give it some kind of input, and then it performs some kind of computations and produces and output:
The important thing about this definition is that it is absolutely general. As long as there is a way to produce an f(x) for every x, then that defines a function. We have no specific restrictions on how this might be accomplished. In that vain we may think of a function in an even more abstract way, as a relation between two sets, "x", and "f(x)", such that for every "x", there exists one and only one "f(x)".
In the most general sense, a function can be defined by simply specifying the output for every possible input. Usually however this is impossible simply because the possible inputs are often infinite. Almost any function you'll encounter in high school and college mathematics can be defined with a simple formula. In our case, almost all functions we'll work with can be defined using a "formula" of sorts, however most will be far more complex than anything encountered in high school. A few will not even have a formula at all, but a "definition". Don't worry too much at this point however, because we'll have plenty of time to practice with functions before we get to the more complex ones.
What is a Recursive Function?
A "recursive function" is just a special type of function. In the most fundamental sense there is nothing special about a "recursive function", it is just another function, in that a recursive function takes an input and produces an output.
What is special then about a recursive function? A recursive function is a function that contains itself in it's own definition! This might sound like it would invariably lead to a contradiction, but this is not so. It is true that if an output calls itself it must be circular. For example:
f(n) = f(n)+1
If we tried to evaluate f(3) for example we get:
f(3) = f(3)+1 = f(3)+1+1 = f(3)+1+1+1 = ...
This process will never end, and we'll never determine what f(3) actually is. Although you might conclude that the string of ones produced proves that f(3) = infinity, this is not how we think about recursive functions. The output of a recursive function is only meaningful if it can be arrived at in a finite number of computations. We say that a recursive function is "non-terminating" when it never produces a final output, and we say that a non-terminating value is "undefined". So f(3) is not "bigger than any finite number", it's simply disqualified from the race. In the large numbers game infinity is as good as zero. We shall treat non-terminating functions rather as broken machines which never produce a coherent output.
So how does a recursive function contain itself without leading to a never ending computation? It achieves this by having every output make a call to another output besides itself, except for one, the initial output. With just a slight alteration, the above definition becomes meaningful:
if n>1 then f(n) = f(n-1)+1
otherwise f(1) = 1
Now if we try to evaluate f(3) we get a definite result in a finite number of steps:
f(3) = f(3-1)+1 = f(2)+1 = f(2-1)+1+1 = f(1)+1+1 = 1+1+1 = 2+1 = 3
So f(3) = 3. In fact, it should be fairly obvious that f(n) = n, since f(1) = 1, and f(2) = f(1)+1, and f(3) = f(2)+1 etc. We can therefore redefine f(n) as:
f(n) = n
Notice that this is no longer a recursive function. This is what we may call an "explicit" form (in otherwords a non-recursive definition). An explicit form is one that gives us a single simple formula for evaluating a recursive function, without having to go through all of the steps. It doesn't make reference to itself. Rather it simply returns the input as the output. Does an explicit form always exist? No, not always. Sometimes the function is simply too complex to be put into a simple formula using additions, subtractions, multiplications, and exponents.