Intermediate Programming Instructor: Greg Shaw
Computer Programming II Instructor: Greg Shaw
COP 3337
Recursion
(see Recursion)
I. What is Recursion?
• Recursion is a powerful technique that breaks up complex problems into simpler ones
• The term recursion derives from the fact that the same computation recurs, or is used repeatedly
• In programming, recursion occurs when a method calls itself repeatedly
• Many problems that can be solved recursively also have simple iterative solutions (i.e., can be easily solved non-recursively using a loop). However, the value of recursion is that some problems may be solved much more easily using recursion than iteration
• For some problems, recursion is the most natural way to think about a solution
• A bonus is that recursive solutions may also require considerably less code that iterative ones
II. How Recursion Works
• A recursive solution works by applying the solution of the problem to progressively simpler inputs.
• For the recursion to terminate, there must be special cases for the simplest inputs. (These are sometimes called the “trivial cases”)
• On each recursive call, the problem is solved for a simpler input (aka: a “reduced case”) until eventually the trivial case is reached and the original problem is solved (i.e., no more recursive calls are made).
III. The Two Requirements for Recursive Solutions
1. Each recursive call must simplify the problem in some way
2. There must be one or more trivial cases (i.e., cases handled directly, without recursion (otherwise, “infinite recursion” will occur)
Problems that meet these requirements have recursive solutions. That is, they have one or more trivial cases that are easily solved, and all other cases are solved by applying the solution to a reduced case of the problem.
IV. The Secret of Recursion
“Assume your method works!”
The call pattern of a recursive method looks pretty complicated, and the key is simply not to think too much about it.
In the getArea of Triangle.java, note how we first check for the trivial cases where the width is 1 or 0.
Then, we have
Triangle smallerTriangle = new Triangle(width - 1) ;
int smallerArea = smallerTriangle.getArea() ;
This creates a smaller Triangle object – getting closer to the trivial case – and computes its area recursively.
The next statement
return smallerArea + width ;
computes and returns the area of the larger triangle.
The trick is to assume the getArea method works! And why shouldn’t we? It obviously works for the trivial cases – the area of a triangle of width 1 is 1. For the other cases, isn’t it true that the area of a larger triangle is equal to the area of a “smaller by width 1” triangle plus the width of the larger?
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- computer science programming virginia department of
- alice an introduction to programming using virtual reality
- intermediate programming instructor greg shaw
- computer programming university of nebraska lincoln
- intermediate programming
- computer programming rock creek schools
- computer programming ii
- recursions computer science
Related searches
- mcgraw hill instructor log in
- shaw direct channels ontario
- bill shaw gold royalties
- shaw innovation
- shaw router settings
- shaw and mckay s theory
- shaw and mckay juvenile delinquency
- shaw and mckay s social disorganization
- concentric zones shaw and mckay
- shaw and mckay study
- shaw and mckay social disorganization
- clifford shaw and henry mckay