Solving difficult problems with recursion -- Part I

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.


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

Dig deeper on iSeries ILE programming

0 comments

Oldest 

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:

-ADS BY GOOGLE

SearchEnterpriseLinux

SearchDataCenter

Close