Recursion - when to use it, when not to use it
Recursion is when a subprogram calls upon itself, either directly or circularly. Circular recursion takes place when there is a list of subprograms s0, s1, ..., sn-1 such that for each index i, si calls upon s(i+1) mod n - i.e.,
s0 calls s1, and s1 calls s2, and ..., and sn-2 calls sn-1, and sn-1 calls s0.
When used properly, recursion is a powerful programming technique. Often, an algorithm expressed recursively requires much less code than would the same algorithm expressed nonrecursively.
Typical good uses of recursion are in "Divide and Conquer" algorithms. These are algorithms for which a large problem is divided up into smaller problems of the same type; each of the smaller problems is solved; and the partial solutions are "stitched together" to obtain a solution to the original, large problem. (In the following, you need to know that merging two sorted lists means combining the lists into a single sorted list.) For example, the Merge Sort algorithm for sorting data may be expressed as follows:
Merge Sort - given an unsorted list L of data, sort the data, as follows:
If the list L has at least 2 items (and therefore has the possibility of data out of order), then
Divide the list L into two smaller lists L1 and L2 of approximately equal size (thus, each of L1 and L2 has about 1/2 of the data of the original list L).
Recursively, apply the Merge Sort algorithm to L1, so that at the end of this step, L1 is sorted.
Recursively, apply the Merge Sort algorithm to L2, so that at the end of this step, L2 is sorted.
Merge the sorted lists L1 and L2 to obtain the sorted list L
Notice that recursion is a form of looping. For example, in the discussion above, when we apply the algorithm recursively to L1, the list L1 has at least 2 items then it is divided into smaller lists, say, L11 and L12; if L11 has at least 2 items, it is subdivided into, say, L111 and L112; etc.
Because direct recursion (a subprogram calling itself directly) is a form of looping, it can often be avoided when its only motivation is looping. Languages like C++, BASIC, COBOL, and Visual Basic provide other loop forms for programmers to use that will often be more clear than recursion, so that, unless there is a motivation other than looping (such as divide-and-conquer), it may be preferable to avoid direct recursion. (There are programming languages such as LISP and PROLOG in which recursion is the primary form of looping - in such languages, it may be impossible or undesirable to avoid direct recursion even when looping is the only motivation.)
Circular recursion is rarely necessary, and often is difficult to understand. Unfortunately, many beginners use circular recursion where a more conventional form of looping would be much easier to understand. Consider the following forms, in which the example on the right is preferable:
