Explicit vs. Recursive Programming

From an academic perspective, recursion seems rather elegant and it requires less code to run. Plus, many algorithms are easier to express recursively than explicitly (without recursion). There is much to recommend recursion. However, expressing an algorithm recursively is not always the right thing to do. For one thing, it is difficult to predict the amount of memory and time consumed by a recursive implementation. Many applications in industry require tight and known runtimes. Memory availability is limited as well. Every time a recursive call is made, more memory is occupied, which takes additional time.

An example is an experience where two offerings of code were made to solve a particular industrial problem. One was recursive. The other was explicit. When tested on the equipment upon which the code was to run, the recursive version ran out of memory for even the simplest case. The explicit case operated fine well-beyond the most complex cases that could be produced in reality. It is interesting to note that the recursive version had only six lines of code, whereas the explicit version had 300 lines of code. One can argue as to which was more understandable to the human reader or which was more "elegant". But, one can not argue as to the effectiveness of the codes in the situation within which they had to operate.



The next few pages will introduce this area of discussion to you and provide a few illustrations. You will notice a number of call trees. These portray the relationship of functions and their data that come to reside in memory as a recursive process proceeds. Pay particular attention to this topic since a problem is not "solved" until it operates in the stark reality of industrial situations.

Last modified: Friday, January 27, 2023, 5:04 PM