 Easier Than Deciphering the Meaning of Life. Really...It is. |
Introduction
As you no doubt have already guessed, this is a tutorial intended to introduce people to the concept of recursion, and its applications in mathematics and computer science. Considering that anyone reading this should be someone interested in one of those topics, this should be a very useful tool in your future. Let us start off with some definitions, so that we’re on the same page as to what is being talked about.
General Recursion
| Definition 1.) Recursion: |
|---|
| A method of specifying a process by means of itself. |
More precisely, recursion is defining large and unwieldy problems in terms of a smaller and more easily solvable problem. "Complicated" instances of the process are defined in terms of "simpler" instances, and the "simplest" instances are given explicitly. Most likely you are asking how that actually simplifies the work, as it probably sounds like more labor. However, you’re getting ahead of yourself, so shut up and wait until the section "How does recursion make my life easier?".
 |
|
| This picture shows an everyday object such as a worm defined recursively. Let's say if our pet earthworm here becomes severed, both halves grow into another worm. Therefore, a whole worm could be thought of as a slightly smaller worm plus a new worm created by the split. This would be the second line of the picture. In the end, the worm can be thought of as a lot of little 'worms'. Later we will see that the smaller 'unit worms' that can define any larger worm is called the base case, and the fact that a larger worm is a smaller worm plus a unit worm here is simply logic, but this would be what we'll soon call the inductive step. |
Recursive Functions
| Definition 2.) Recursive Definition of a function: |
|---|
| A way of defining a function using recursion. |
This may seem to be a little vague, but once we understand what the concept of recursion is, and how it works, recursively defined functions
become easy to understand. This way of defining a function is alternative to the direct method, which everyone is familiar with from algebra.
|
| |
| Direct Implementation | Recursive Implementation |
| f(x)=30x+7 | f(x)=f(x-1)+12x |
This method of defining a function requires the following two items to make any sense: a base case, and an inductive step (or recursive step, as in the textbook by Rosen, see resources page). These itmes are used to define successive values of the original function in terms of smaller values fitting the same pattern (such as defining the big worm in terms of the smaller worms). This leads us to the following definitions.
| Definition 3.) Base Case of a Recursively Defined Function |
|---|
| A value or values for which the recursive function is concretely defined. |
Usually, the recursive function is set up in such a way that the base case is eventually reached by successive values of input. The use of proper base cases is necessary for a recursive function to ever make any literal sense (we'll talk about why later).
| Definition 4.) Inductive rule/step in a Recursively Defined Function |
|---|
| A relation between successive values that result from the given recursively defined function. Or in other words, some type of rule that logically defines a certain value of the function in terms of smaller or simpler |
The inductive rule must also work towards the chosen base case in a valid recursive definition. We'll talk about why this is a bit later. The definition of a recursively defined function may sound a little bit like circular reasoning, but if you think about it, it makes sense. But don’t think about it too hard, we wouldn’t want you to hurt yourself. Anyway, what this means is the following: suppose you had some crazily complex function f(n) that's too complicated to define directly. Following it out for a couple of input values, you notice a pattern. You find f(0)=12, and each following value is 7 more than the previous. By logic that we’ll discuss later, you could then define a rule for finding values (7 more than the previous value), as f(n)=f(n-1)+7.
In the above example, the defined base value (f(0)) is the base-case, and the function f(n)=f(n-1)+7 is the inductive/recursive rule that defines f(1) as f(0)+7, f(2) as f(1)+7... etc. Now what about that last part about the function approaching the base case? That is going to be covered in later sections in more depth, but it simply warns that if the inductive rule doesn’t work in the direction of the base case, you will get an infinitely expanding recursive definition.
Recursive Algorithms
| Definition 5.) Recursive Algorithm: |
|---|
| An algorithm that calls itself with smaller and smaller subsets of the original input, doing a little bit or work each time, until it reaches the base case. |
Pretty much, a recursive algorithm is simply an application of a recursively defined function. A recursive algorithm uses the time-saving techniques granted by recursion (which we'll speak of later) in a relatively simple format. The algorithm is just a recipe for finding a particular value given by a recursive definition by using the inductive rule to work towards the base case. This is the only value that the function is directly defined for, so every other value must be derived from it using the structure of the recursive definition. For an example of this point, we can use the above recursively defined function to make a recursive algorithm to find F(n).
|
|
|||||||||||||||||||
Instead of just using a formula to directly compute the value f(n), the recursive algorithm calls itself for f(n-1), and adds 7 to that resultant value. However, when the function calls f(n-1), it will call the function again for f(n-2) and add 7 to that value and return that to the previous call of the function. These steps will keep happening until the function is called for the base case of f(0), at which point 12 will be returned. Man, that’s a mouthful. Don’t get discouraged if that seems complex, a recursive algorithm can quickly flower out into a large amount of open iterations of the recursive method. We’ll leave the deeper explanation of what’s happening until the section "How does recursion work?" Next, we’ll get a little deeper into what all this means, and why we care.
Site Created By Dillon Sadofsky and Leo Glass