The basic idea behind a recursive function is that you can solve a problem by breaking it into smaller pieces, solving each of those smaller pieces by breaking them up into even smaller pieces, and so on.
Mathematical induction is an indirect method of proof. It is particularly useful when dealing with recurrence relations. Recurrence relations are recursively defined functions. In the description of mathematical induction in the lecture notes, 'N' refers to any natural number N (N >= 0). S is some function which takes an integer (natural number) as its argument. 'k' is some fixed natural number. You don't need to be able to do mathematical induction proofs for this course.
The example of mathematical induction given is a proof that the sum of the natural numbers from 0 to N is equal to N * (N + 1) / 2. If you've never seen this before, you might want to try it for yourself with a few examples:
0 + 1 + 2 = 3 = 2 * 3 / 2 = 2 * (2 + 1) / 2
0 + 1 + 2 + 3 = 6 = 3 * 4 / 2 = 3 * (3 + 1) / 2
etc...How many values of N would you have to try before you would KNOW it was true? If you caculated 0 + 1 + ... + 100 and determined that it was equal to 100 * 101 /2, would you be convinced? Could you be sure that it wouldn't fail for N=101? With mathematical induction, you can prove the validity of the equation.
In the description of recursion, the most basic form of a recursive function is given. It highlights the two basic parts of a recursive function:
- the base case - without a base case, your recursive function will never terminate. For functions of natural numbers, N=0 is usually the base case.
- the recursive part - this part implements the concept that you can 'solve the problem' by solving a smaller problem. If this doesn't make sense to you right away, don't worry about it. Your intuition will improve with practice.
The example function that's given computes the sum of the natural numbers from 0 to N. The important thing to understand here is that the sum of the natural numbers from 0 to N is equal to the sum of natural number from 0 to N-1 plus N. Read that again. Yes, it sounds trivial. But that's what makes recursion so powerful: its elegant simplicity. In writing recursive functions, you need to be able to think about problems like this. Sometimes, using actual numbers can help.
Example: If I tell you that I have a function f() that can compute the sum of numbers from 0 to 100 and then ask you to compute the sum of numbers from 0 to 101 using that function, you could easily write the expression f() + 101 to give me the correct answer.
If you understand that example, you just need to generalize that idea to understand the example function given in the lecture notes.
(See sections 2.5 and 5.1 of Sedgewick.)
Iteration and recursion - in principle, any function that can be written recursively can also be written iteratively, and vice versa. For the example function given in slide #1, the equivalent iterative function would be:
int f(int N) { int count, sum = 0; for (count = 0; count <= N; count++) sum = sum + count; return sum; }(You could also use a while loop...)
Sometimes it is quite difficult (or unnatural) to create an equivalent iterative version of a recursive function. The iterative program may be 20 completely indecipherable lines of code, while the recursive program is only 3 lines of code. This is why recursion is such a powerful programming tool. Some programming languages, in fact, have no while or for loops, only recursion.
"Divide and Conquer" - A recursive version of your bisection programming assignment (#1) is given. Try to trace through the code and prove to yourself that it does the same thing. Notice that there are two recursive 'return' statements in this function but that only one of them can be executed. (Notice also that the 'else' is unneccessary.)
In thinking about divide and conquer type problems, you should again remember the overall concept of recursion - solving a big problem by breaking it into smaller problems.
(See section 5.2 of Sedgewick's book.)
In the bisection function, f() is the function for which you are trying to find a root. This example demonstrates that if you use the function:
int f (int k) { return v - a[k]; }You can use the bisection function with 'l' and 'r' set to 0 and the size of the array to determine whether 'v' is a value which is in the array a[]. (Notice that this function will only work if the array is sorted. why?)
The example given for v=144 shows the values of l, r, m, and whether f(m) is positive or negative for each execution of the function f(). (After the first call, f() is called recursively 3 times before terminating.) Try tracing through the function with a value not in the array to see how the function will work in that case.
Two examples of problems for which the straightforward recursive solution is not computationally efficient are given. The first computes binomial coefficients (Pascal's triangle); the second computes 2^N (in a very inefficient manner). The tree-like illustration of the 2^N function is something you should be able to generate. Drawing trees to trace through recursive functions is an effective method for understanding/debugging recursive functions.
Dynamic programming is offered as a technique which can be used to make recursive functions more efficient. The basic idea of dynamic program is that you use an array (or some other appropriate data structure) to save intermediate results and avoid duplicating computations.
(See sections 5.1 and 5.3 of Sedgewick.)
It's important to understand that recursive functions do not execute any differently than normal functions in C. They are still 'called' from another function. Execution stops in the calling function, until the 'called' function returns. Parameters are passed in the same way. The only thing that's different is that the function which is calling the recursive function may be itself.
One way to think about how functions are executed, which may help, is to imagine that the code of the function is actually copied over the function call. Here's an illustration of that idea:
A non-recursive function call:
int f (int k) { return k + 2; } void main() { int y; int x = 5; y = f(x); printf("y is %d\n", y); }You can think of the above example as being equivalent to this:
void main() { int y; int x = 5; y = x + 2; // copy the code of f() here, with k replaced by x printf("y is %d\n", y); }It should be plain to see that both versions are equivalent.
You can trace through a recursive function be repeatedly 'pasting' in its code whenever it calls itself. Example (factorial function):
int f (int n) { if (n == 0) return 1; return n * f(n - 1); }Let's trace through the function with the pasting technique for n=4:
f(4) { if (4 == 0) return 1; // n is 4 here return 4 * f(3) { if (3 == 0) return 1; // we just 'pasted' the code here return 3 * f(2) { if (2 == 0) return 1; //n is 2 here return 2 * f(1) { if (1 == 0) return 1; return 1 * f(0) { if (0 == 0) return 1;Now what? Well, we've finally gotten to the base case. We don't need to 'paste' again, because we don't get to that line. We just return 1 here. (You can see why base cases are so important - without them, we'd never finish 'pasting.') We haven't finished yet, though...
f(0) just finished its execution. There's no mystery about what happens next. Whenever any function finishes (returns), its return value (if any) is returned to the calling function and execution resumes there. Make sure you understand this - it's critical.
So, the value 1 is returned. In the function f(1), we were executing the line "return 1 * f(0)" when f(0) was called. So, we continue: f(1) will return 1 * 1 to its current function: f(2). Then, f(2) will return 2 * f(1), which is 2 * 1. Next, this value, 2, is returned to f(3), so f(3) finishes by executing the line: 3 * f(2). The number returned by f(2) is 2. Thus, 3 * 2 is returned by f(3), and we're done - with the correct result, 3.
An alternative way to think about the execution of a recursive function is with a pushdown stack:
For our example, the stack would have the following sequence of values: (read from left to right)
f(0) 1 f(1) f(1) f(1) 1*1 f(2) f(2) f(2) f(2) f(2) 2*1 f(3) f(3) f(3) f(3) f(3) f(3) f(3) 3*2
Programming assignment 4 is a heuristical method for solving the problem. By heuristic, we mean that we do not actually get the bets tour possible, only a good one, we hope. Later in the course we will see why we had to resort to heuristical methods for this problem.
This function is somewhat difficult to follow. Notice that visit() recursively calls itself. Don't be overly concerned if you have trouble understanding it. Come back to it later after you've worked on programming assignments 4 and 5.
swap() can be thought of as a function which exchanges the order of two points on the tour
checklength() can be thought of as a function which calculates the total distance of the tour for the current ordering of the points. You should also assume that it somehow records the order of the points if it has found a tour which is shorter than the best tour found so far.
Recursion is a powerful programming tool. Also, it's great for drawing pretty pictures! (Also, see Assignment 5.) Some other 'famous' recursive problems are discussed in Sedgewick section 5.2