Tip

Solving difficult problems with recursion -- Part I


Ron Turull

Recursion is one of the most powerful problem-solving techniques in computer science, and learning to use it will give you a decided edge in boosting your programming skills. RPG -- the most popular language on the iSeries -- does not support true recursion, which involves a program calling itself either directly or indirectly. However, ILE RPG does support recursion at the procedure level. That is, a procedure can call itself (either directly or indirectly), but a program cannot. (OPM RPG does not support recursion at all.)

How recursion increases efficiency
Recursion is a type of divide-and-conquer technique used to solve difficult programming problems by reducing a problem to simpler, but identical, "sub-problems." The sub-problems are then reduced to "sub-sub-problems." This multi-step reduction process continues until a trivial case is reached. The solutions to each sub-problem, starting with the trivial case solution(s) at the lowest level and working upward to the final solution to the original problem, are then combined to produce solutions to the next higher level of problems.

More Information

Consider an example of five people assigned to count a big bucket of marbles. Instead of having just one person count the marbles while the other four stand around and drink coffee (a technique which I call the "road crew" method), it is much more efficient to divide the marbles into five roughly equivalent groups and have each person count the marbles in one group, then add the sub-counts together to produce a final count. This is a recursive solution, and it is not limited to this single level of sub-counts. For example, if the sub-groups of marbles could not be easily counted, each person could divide his group into five groups and recruit four other people to count the sub-sub-groups. This could go on until the number of marbles in each group could easily be counted by a single person (the trivial case).

When to use recursive algorithms
There is no single recursive algorithm. Rather, recursion is a type of algorithm. Problems that can be solved using a recursive solution must have the following two characteristics:

  1. The problem must be able to be stated in terms of simpler yet identical sub-problems.
  2. There must be a trivial case that is easily solved.

A simple example will help explain. Consider the factorial problem. The factorial of a number (an integer) is the result of multiplying that number by each of its preceding positive (non-zero) integers and is represented by the mathematical symbol "!" (e.g., 4! = 4*3*2*1 = 24).

Factorials can be solved rather efficiently by a simple do-loop. However, they can also be solved using a recursive approach because they have the two characteristics described above. Namely:

  1. Stating the problem in terms of sub-problems. Looking at the solution to 4! we can see that 4! = 4 * (3!) because 3! = 3*2*1. In general, N! = N * (N-1)!. This is simpler because it involves the factorial of (N-1) instead of N, yet it is identical because it involves a factorial.
  2. The trivial case. The trivial case in the factorial problem is the factorial of 1 (or 1!) which equals 1.

Looking ahead
In Part II, we will discuss how you go about coding a recursive solution, and we'll see some examples. We will also talk about when you should use recursion and when you should not.

-----------------------------------
About the author: Ron Turull is editor of Inside Version 5. He has more than 20 years' experience programming for and managing AS/400-iSeries systems.


This was first published in July 2005

There are Comments. Add yours.

 
TIP: Want to include a code block in your comment? Use <pre> or <code> tags around the desired text. Ex: <code>insert code</code>

REGISTER or login:

Forgot Password?
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy
Sort by: OldestNewest

Forgot Password?

No problem! Submit your e-mail address below. We'll send you an email containing your password.

Your password has been sent to:

Disclaimer: Our Tips Exchange is a forum for you to share technical advice and expertise with your peers and to learn from other enterprise IT professionals. TechTarget provides the infrastructure to facilitate this sharing of information. However, we cannot guarantee the accuracy or validity of the material submitted. You agree that your use of the Ask The Expert services and your reliance on any questions, answers, information or other materials received through this Web site is at your own risk.