Recursion
Document: Software Engineering 1: Course Notes
Term 2: Weeks 11-20
Week 8-10: Chapter 2 pp. 20-26
Preferences?
Alcock chooses to introduce recursion toward the end of
Chapter 2. I'm not sure I agree with the need for this.
Recursion - functions which invoke themselves - is an interesting
programming concept, and it does permit very elegant solutions to
certain programming problems. On the other hand, there is never
a situation where the same effect as recursion cannot be achieved
using conventional iteration mechanisms, such as for
statements.
In any case, all I will add to Alcock's discussion are the
following brief comments:
- When any function is invoked, storage is allocated for its
local variables (including parameters, if any).
- This storage will be deallocated when the function
terminates.
- Recursive functions are a special kind of function. This
may seem trite, but it follows that you need to understand the
general concept of a function reasonably well before you
try to understand the idea of a recursive function...
- If a function is invoked again while it is still already
active - i.e. if a recursive invocation is made - then
additional storage is allocated to hold a new set of local
variables for this new invocation. Each invocation thus has an
entirely separate set of variables and parameters - even though,
within each invocation, these are referred to by the same names.
There is no confusion because the computer keeps careful track of
which invocation is being executed, and therefore which copies of
variables or parameters to refer to.
- At first sight it seems that recursive function invocation
must be fatal: surely the computer will be caught in an infinite
regression, invoking ever more copies of the same function, until
something horrible happens (like it runs out of storage to hold
any more variables) and the whole thing crashes? This certainly
can happen; but recursion can also be made benign. It is
made benign by ensuring that, at each nested invocation, something is changing (typically a parameter value); and at
some, finite, point, this will result in a copy of the function
which does not make a further, nested, recursive call to
itself, but instead terminates. That then allows its caller to
terminate, and its caller in turn, so that the whole nest of
recursive calls can finally unwind, and return control to
wherever the very first instance of the function was called from.
- But recursion will only be benign and controlled in this
way if you, the software engineer, make it so. Recursion is
intrinsically dangerous stuff - use it with extreme caution!
Document: Software Engineering 1: Course Notes
Term 2: Weeks 11-20
Week 8-10: Chapter 2 pp. 20-26
Preferences?
McMullin@ugmail.eeng.dcu.ie
Wed Mar 15 10:20:49 GMT 1995