So recursion is basically for accumulating the result of an unpredictable number of operations.
Well, it doesn't always have to be an ``accumulated'' result -- just one that is reached by a process of progressive simplification down to some limit. For instance, you can use recursion to figure the ``integer square root'' of any non-negative integer n -- the largest integer whose square does not exceed n.
Why wouldn't you just take the square root of n and throw away the fractional part?
You could do that, but when the square root is irrational the computer generally represents it internally using an approximation to the true value. If n is large, the approximation can be off by more than 1. The recursive approach gives an exact and correct answer for any non-negative integer n.
So how does it work?
At all times, the recursion keeps track of two numbers, one of which (the ``lower bound'') is known to be less than or equal to the correct integer square root, while the other (the ``upper bound'') is known to be strictly greater than the integer square root. These two numbers act like fences enclosing the integer square root. If we ever reach a point at which the bounds are only one unit apart, we'll know that the lower bound is the integer square root, because it can't be less than the lower bound and can't be greater than or equal to the upper bound, and there just are no other integers for it to be. So that's our stopping point.
OK, but how do we reach it? If we're just given n, its integer square root could be anything.
No, not absolutely anything. An integer square root can't be less than 0, and the integer square root of n is always less than n + 1.
So our bounds are 0 and n + 1. How do we bring them closer together, so as to close in on the real integer square root?
Determine the average of the lower and upper bounds and square it. If the result is greater than n, we can bring the upper bound down to the average. Otherwise, we can move the lower bound up to the average. In either case, the range of integers enclosed between the fences is smaller than it was before. If the fences are one unit apart, we're done; otherwise, repeat the process. Here's what it looks like in Scheme
(define (adjust-fences n lower-bound upper-bound)
(if (= (add1 lower-bound) upper-bound)
lower-bound
(let ((average (half (+ lower-bound upper-bound))))
(if (< n (square average))
(adjust-fences n lower-bound average)
(adjust-fences n average upper-bound)))))
Now it's easy to define the integer-square-root procedure:
(define (integer-square-root n) (adjust-fences n 0 (add1 n)))
Next topic
Previous topic
Table of contents
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/scheme-web/integer-square-root.html