CS202 Study Guide
Unit 6: Recursion
6a. Define linear recurrence and give examples
- What is recursion? Refine that definition for linear recursion.
- When is recursion an appropriate implementation approach?
- What are the three drawbacks of recursion?
Recursion is a technique often used in computer science to define a function by itself. To do this, the recursive function first partially solves the given problem or divides it into several sub-problems and then calls itself with these new sub-problems. This continues until the problem is completely solved or the solution is broken down into trivial individual parts.
Recursive solutions are often more elegant, easier to find, easier to check for correctness (e.g. using mathematical induction), and easier to explain than iterative approaches. But, they are less efficient, from a computational perspective, due to the many function calls and attendant memory use, both of which are difficult to predict when recursion is employed. That is why, in the case of performance-critical programs, especially in hard-real time embedded systems having limited resources, it often pays to use purely iterative approaches rather than recursion. Since recursive and iterative functions are equally powerful, there is an iterative equivalent for each recursive implementation.
Linear recursions are recursions in which there is a maximum of one recursive call per recursion step. The calculation runs along a single chain of calls. Linear recursions can be resolved very easily. As the number of recursive calls per step increases, however, conversion to pure-iterative becomes more difficult.
Be careful when choosing recursion vs. iteration. This writer has found that embedded systems should generally not use recursion, whereas non-embedded systems tend to have the resources to support recursion and not have strict timing constraints.
Review:
6b. Explain important recursive functions
- Where does one find recursion applied in a practical way?
- Within mathematics and computer science, how is recursion defined?
- What are the three requirements for recursion to be applied effectively?
Recursion appears in many fields of work, including art and literature, not just mathematics and computer science. One can see this in the general definition, "Recursion is the process of repeating something in a self-similar way". One usually sees recursion defined in terms of computer science as a function that calls itself. While that is true, in its own limited way, it does not embrace recursion's extensive application.
From the perspective of mathematics and computer science, "Recursion is the process of describing an action in terms of itself. Generally, one has functions that call themselves, an initialization case that describes conditions at the start, and a base case that gives a specific situation when the recursion will cease and a final result produced".
Review:
6c. Produce recursively defined sequences
- Why is practice important when learning to apply theory?
- Why is the transition of theory to application necessary?
- What is the essential nature of an expert?
Practice makes perfect. An old colloquial sentiment but very very true nonetheless. It is often the case that ancient advice is the best advice. This learning goal encourages us to consider how various equations can be cast in a recursive manner. By looking at a wide range of examples, the theory behind recursion will begin to "click", to come together in clarity and usefulness.
Clarity and usefulness are essential to the transition of theory to practice. Given the imperfect world in which we live, the infinite accuracy of mathematics cannot be fully implemented. For instance, a computer cannot even divide 1 by 3 accurately. Yet, we still need programs that reflect theory. We still need bridges to stand up to heavy use. We still have to make justifiable implementation decisions.
Review Explanation and Examples.
6d. Write recursive relations that are defined in terms of themselves at increasingly earlier moments in time
- In what way do data sequences relate to data over time?
- What are potential benefits of gathering data on a temporal basis?
- What are the limits of human observation of temporal data?
The acronym IoT stands for "Internet of Things". What that comes down to is the generation, transmission, analysis, and application of data over time within a specific situation. We have studied data sequences. In this case, we are talking about data
that arrives over time,
(Dt0, Dt1, Dt2, ...).
An example is determining machine faults via sound. This figure shows data derived over time during a machine's operation. The left graph is due to digitized sound. The right graph is an analysis that shows abnormal variations in that sound. Once variations are analyzed, it is possible to determine whether or not the machine needs maintenance or is about to fail.
It is rarely possible to have someone listening to a machine or watching an evolving graph with a long enough attention span to catch every variation. This unlikeliness increases as the number of machines increases. The same is true of complex systems with numerous data generators. An example is a modern aircraft and its plethora of internal sensors. A home is another example. For instance: smoke, fire, gas, and temperature sensors that can tell inhabitants well ahead of time that something is wrong.
We can easily see that data over time is important if we are going to be aware of important situations and take appropriate action.
Review Predicting Data Sample Values.
Unit 6 Vocabulary
This vocabulary list includes terms you will need to know to successfully complete the final exam.
- attendant memory use
- embedded systems
- function calls
- iterative approaches
- iterative equivalent
- linear recursions
- non-embedded systems
- recursion
- recursive function
- recursive implementation
- recursive solutions
- sequences