You thought we were done with OOP theory, well you were wrong! :-) I wanted to make sure to mention this at some point in the class, and this week, being a light one, is as good as any.
There are three and only three relationships that objects can have:
The following code snippet illustrates each case:
class Truck extends Vehicle { Engine eng; GasTank tank; ... int fillUpTank (Gas g) { ... } int repairEngine (Tools t) { ... } ... }
Truck has an is-a relationship with Vehicle, because it is a descendant.
Truck's relationship with Engine and GasTank is has-a because they are properties of Truck.
Truk has a uses relationship with Gas and Tools because it takes them as parameters to its methods.
Note: If you ever use a more "pure" OO language (like Java or Ada), these are the only relationships your objects can share, since no code can exist outside of a class namespace.
Definition A recursive function is a function which calls itself.
The idea of recursion is to reduce a complex problem to a smaller instance of itself. Once the problem has been reduced to the simplest instance possible, we then solve that simple case and we're done.
(p. 591-592) In order for a recursive function to work properly, there are three requirements.
Look at the tiny IF block about a third of the way down page 592 for a stripped-down example of how a recursive function should look.
There are two phases to a recursive call:
The following code snippet illustrates where these phases occur in code:
void recursive_proc(String arg) { // This is the winding phase some_code(arg); ... // This is the exit condition if (arg.length == 0) return; // This is the recursive call recursive_proc(arg.substring(1)); // This is the unwinding phase some_other_code(arg); ... }
Infinite Recursion occurs when you don't implement an exit condition, or don't implement it correctly.
(p. 596) Stack Overflow is the most common exception encountered when dealing with recursive programs. Each time you call a function (recursive or otherwise), a hunk of memory called the stack frame is allocated on the program stack for storing the function's parameters and local variables. As you can imagine, recursive functions push a lot of frames onto the stack. A stack overflow exception will be raised if you don't have a propper exit condition in place (a side effect of infinite recursion), or there are simply too many calls in the winding phase for the available memory in the machine.
There are a few more involved forms of recursion.
A function f1 calls f2 which calls f3 which calls f1. This kind of recursion is more complex and potentially more hazard-prone. Fortunately, you will rarely need to use it. Some complex data structures (such as N-way trees) might require that you use indirect recursion.
A function is said to be tail recursive if the recursive call is made as part of the return statement and the call is not part of an expression.
We should make functions tail recursive when possible because most compilers can optomize for them. When the recursive call happens, the program does not need to push another fram onto the stack. Instead, the compiler simply replaces the last stack frame with the results of the current stack frame. This makes it possible to recurse very deeply.
Maybe we'll do an example of tail recursion in class.
It is worth noting that every recursive function can be implemented in an iterative fashion instead (i.e. a for loop). For some situations however, recursion is a more elegant approach. An example of a case where iteration might be preferred would be traversing a singly-linked list. For an example of a problem which can be solved with either recursion or iteration, see the Factorial examples on page 598-600.
There are numerous situations that lend themselves to recursion. Many math functions can be solved with recursion. Some examples:
Recursion is performed in Ada as it is in any other procedural language. There are no special keywords or constructs that you need to learn here.
Write a program containing a recursive procedure that finds and prints all the factors of a Natural number. This program will be amazingly short.
Hints: The recursive procedure will require two arguments, both Naturals. You may want to make an additional "driver" procedure that just takes one argument and then calls the recursive function. You don't have to do this, it's up to you.
This assignment is due on December 5th, 2001, the night of the Final Exam!
Oh yeah, Happy Turkey Day.