COMP 130
Elements of Algorithms and Computation
Spring 2012
![[Rice University]](http://www.staff.rice.edu/images/staff/branding/shield.jpg)
Problem decomposition using a functional breakdown of the algorithm is an example of a larger notion in computer science called "delegation". That is, to say that a function consists of calls to other functions is to say that the original function has broken the problem down in to smaller tasks that it delegates to the other functions to perform.
Delegation enables one to separate the individual processes in an algorithm and to express the process at any given point in the most abstract manner as possible. This leads to the simplest and most accurate, direct expression of the algorithm.
Delegation is related to the notions of "encapsulation" and "separation of concerns". Encapsulation is the idea that things can, and should be, treated as "black boxes" which perform particular tasks but without allowing the user to know how that task is performed. In the end, encapsulation is a way of expressing the abstraction of a process or entity. Separation of concerns is the idea that parts of an algorithm or system that do not involve each other should be coded in a manner that enforces that separation, e.g. the code should be completely physically separate with no common variables.
In general, one is always delegating to encapsulated entities.
Encapsulation is usually discussed in terms of objects and the way that objects create a closure that hides the object's internal data. However, the same notion can be applied to functions in that functions also create a local closure that hides its local variables and internal processes. Functions are high-level encapsulated abstractions of processes.
So how does this relate to recursion? Remember that a recursive process is one where the algorithm is defined by breaking down the overall process in to a smaller piece(s) that is processed in the same manner as the larger piece. That is, a recursive algorithm is a delegation to another function to process the smaller piece unless a base case was reached. But since the process to handle the smaller piece is the same as the calling function, the function makes a call to itself, i.e. a recursive function delegates to itself.
Recursion is just a degenerate case of Delegation where the delagatee coincidentally happens to be the same as the delagator.
There is a pitfall in recursive programming (actually, in any sort of delegation scenario) which is that the recursive function must be "re-entrant". That is, the recursive function must be able to be called over and over again, while it is still in the middle of pending processing.
Suppose a recursive function uses a global variable to store data while it performs its processing. What happens when that function calls itself? The problem is that the global varialbe is outside the encapsulation of the function and thus subject to manipulation by other entities, including other calls to the function itself. The recursive call may want to use that same variable to store a different value for its particular processing needs. This will corrupt the data that the calling function was using, destroying its operation! A recursive function must therefore be fully encapsulated in terms of the data that it uses. This is not always so easy, but luckily classes and objects afford us a much larger, richer encapsulation scheme, but that's a topic for another course...