Site Map: MAIN / A Reader's Treasury / This Page
A READER'S TREASURY
Recursive Techniques in Programming
D. W. Barron
Published by American Elsevier/NY in 1975
A Book Review by Bobby Matherne ©2001
Like Us? Subscribe to Receive a Monthly Email
Reminder of New Reviews & New DIGESTWORLD Issues CLICK
In the evolution of consciousness of this one-time computer programmer, I had to own up to the fact that I knew nothing about recursion. I had avoided it like an envelope of anthrax bacteria. The author rightly points out that if computers had existed in the Middle Ages, some programmers (who never thought about recursion) would have likely burned others (those who used recursion all the time) at the stake. What's the big deal about recursion? Well, it's a little like the bootstrap paradox: to get the first program into a computer, you need to load it with the program loader, which is a program itself. So, how does the program loader get into the computer? The feat is seemingly impossible, and yet every time we re-boot our computer we solve that problem, or rather someone has already solved it for us and all we have to do is push a button or so. Recursion is like that - we push a button or call a function and something magical seems to happen all by itself.
To solve the problem of computing the factorial of 3, all we have to do is to multiply 3 times the factorial of 2 which can be calculated by multiplying 2 times the factorial of 1. If you have recursive functions available, the simple solution is F(n) = n*F(n-1), and this will work for all positive values of the integer n. How are we to understand this?
[page 11] . . . if the whole program is represented by a single function, how is one to achieve any sort of repetition? The answer is, by using recursion; recursion is to functional programs what repetition is to command programs. For example, evaluating factorial (3) according to a recursive definition involves calculating factorial (2) which in turn involves calculating factorial (1), so that the repeated invoking of the definition achieves the desired repetition.
Fine. Made very little sense to me at first. I was raised programming with Do Loops where I would repeat the desired instructions n times. But in recursive programming, the looping is implied and thus not visible to the programmer. Plus you need to have a stack to store the intermediate results during the implied looping. Fortunately or unfortunately for me, when I went to the Foxboro Company, their Fortran compiler had recursion as an option, so I had to learn how to use that as a technique. It was quite a stretch for me, but came in handy many times. This book came into my library as a result of my need to learn to apply recursive programming techniques and to understand them.
The author says that, "Recursive techniques play a great part in systems which aim to simulate human thinking - the field sometimes called 'artificial intelligence'." He gives as an example the General Problem Solver of Newell, Shaw and Simon. Imagine you wanted a way to change object a into object b. Now define three processes:
- Transformation: transforms object a into object b.
- Difference reduction: reduce or remove the difference between objects a and b.
- Apply Operator: apply operator q to object a.
Transformation of object a into object b may be described as:
- Reduce difference between a and b.
To reduce a difference:
- Find operator q and apply operator to d.
To apply an operator to d:
- if d satisfies conditions for applying q to d, do so, if not, transform d into an object that does satisfy condition and then apply q to d.
Whether or not you understand all of the steps above, it's easy to inspect the italicized words to find that each of the three steps call one of the other two steps to be performed. Thus, you are presented with a set of three nested and recursive routines that call each other continually until the object a is transformed into object b.
The author leaves us an important caveat about the use of recursive programming and I'll close this review with that. Good maintainable program code is much more desirable than tricky, but obscure coding techniques.
[page 13] The indiscriminate use of recursion is certainly not to be reommended. The programmer must weigh the benefit of a simple program, more easily written, against the extra running time and the possibility of trouble in debugging.
When you are unsure about the use of recursive code, the best recourse is follow this simple advice: "When in doubt, leave it out."
Any questions about this review, Contact: Bobby Matherne
== == == == == == == == == == == == == == == ==
20+ Million Good Readers have Liked Us!
20,454,831 as of October 20, 2018
Month-to-Date Daily Ave 5,832 Readers
For Monthly DIGESTWORLD Email Reminder:
Subscribe! You'll Like Us, Too!
== == == == == == == == == == == == == == == ==
Click Left Photo for List of All ARJ2 Reviews Click Right Bookcover for Next Review in ListDid you Enjoy this Webpage?
Subscribe to the Good Mountain Press Digest: Click Here!
CLICK ON FLAGS TO OPEN OUR FIRST-AID KIT.
All the tools you need for a simple Speed Trace IN ONE PLACE.
Do you feel like you're swimming against a strong current in your life? Are you fearful? Are you seeing red? Very angry? Anxious? Feel down or upset by everyday occurrences? Plagued by chronic discomforts like migraine headaches? Have seasickness on cruises? Have butterflies when you get up to speak? Learn to use this simple 21st Century memory technique. Remove these unwanted physical body states, and even more, without surgery, drugs, or psychotherapy, and best of all: without charge to you.
Simply CLICK AND OPEN the FIRST-AID KIT.
Counselor? Visit the Counselor's Corner for Suggestions on Incorporating Doyletics in Your Work.
All material on this webpage Copyright 2018 by Bobby Matherne