Solving difficult problems with recursion  Part I
Recursion is one of the most powerful problemsolving 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 problemsolving 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 divideandconquer technique used to solve difficult programming problems by reducing a problem to simpler, but identical, "subproblems." The subproblems are then reduced to "subsubproblems." This multistep reduction process continues until a trivial case is reached. The solutions to each subproblem, 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.

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 subcounts together to produce a final count. This is a recursive solution, and it is not limited to this single level of subcounts. For example, if the subgroups of marbles could not be easily counted, each person could divide his group into five groups and recruit four other people to count the subsubgroups. 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:
 The problem must be able to be stated in terms of simpler yet identical subproblems.
 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 (nonzero) 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 doloop. However, they can also be solved using a recursive approach because they have the two characteristics described above. Namely:
 Stating the problem in terms of subproblems. Looking at the solution to 4! we can see that 4! = 4 * (3!) because 3! = 3*2*1. In general, N! = N * (N1)!. This is simpler because it involves the factorial of (N1) instead of N, yet it is identical because it involves a factorial.
 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/400iSeries systems.
Please create a username to comment.