Recursion And Iteration
December 5, 2017
Since Knuth calls it the “grand-daddy of all algorithms,” we examine Euclid’s algorithm for calculating the greatest common divisor of two integers:
(define (gcd-r m n) ; recursive (if (zero? n) m (gcd-r n (modulo m n))))
(define (gcd-i m n) ; iterative (while (positive? n) (let ((t (modulo m n))) (set! m n) (set! n t))) m)
Both produce the same results over a variety of inputs:
(do ((m 1 (+ m 1))) ((= m 1000)) (do ((n 1 (+ n 1))) ((= n 1000)) (when (not (= (gcd-r m n) (gcd-i m n))) (display m) (display " ") (display n) (newline))))
Tracing the recursive version is interesting:
> (gcd-r 35 28) |(gcd-r 35 28) |(gcd-r 28 7) |(gcd-r 7 0) |7 7
To my mind, the recursive version is more readable and easier to write; the iterative version requires an extra variable t to manage the simultaneous assignments to m and n. Both versions perform the same calculations and have the same time complexity; Knuth proves the number of recursive steps is O(log n) in the worst case, when m and n are successive Fibonacci numbers (AoCP Vol2 Sec4.5.3). In languages like Scheme the recursive version is guaranteed to operate in constant space, as the trace shows, but some other languages may blow out the stack during the recursive calls. My preference, of course, is the recursive version, programmed in a language that supports tail call elimination.
You can run the program at https://ideone.com/6cmcce.
In Python, a Fib implemenation. Seems like iterative is a lot faster, but didn’t really optimize the recursive one that much either.
@Rutger: Your algorithms are not the same. The recursive algorithm takes exponential time, the iterative algorithm takes linear time. You might enjoy this program, which is recursive and takes logarithmic time:
I am a big fan of recursion but, to give the iterative version a
bit more credit, it can be rewritten as follows, avoiding both
the temporary variable and the mutations.
I suppose someone may object that this version is thinly veiled
recursion but another could counter that tail recursion is
thinly veiled iteration. Perhaps more to the point, both the
following version and the two versions in the solution generate
iterative processes in Scheme (to use SICP terminology if I
recall correctly), although two of them are iterative programs
and one recursive.
Rutger: The first algorithm is actually horribly bad: it’s exponential, because all the smaller Fibonacci numbers are recomputed over and over. If you make it recursive with memoization, it’s linear but can still blow up your stack due to the recursion if n is large.
@chaw: You don’t need min and max. If m < n, the first call swaps them.
I used the temporary variable in the iterative version on purpose, because it is needed in languages that don’t allow simultaneous assignment.
A tail call is just a goto combined with a simultaneous reassignment of local variables. The reassignment part can make code clearer and less error-prone (since we are less likely to forget to modify a variable appropriately) but really both are just different ways of expressing the same underlying computation.
Converting a non-tail recursion into an iterative form can be interesting though. Here’s the naive fibonacci implementation, in Javascript:
Neither recursive call is in tail position, but we can build up the final result in an accumulating parameter, passed between the two calls:
Now one call is in tail position and can fix the other with an explicit continuation function:
To get properly iterative, we can replace the continuation functions with a stack (containing the stored values of n), use an explicit loop and in-place modification everywhere:
As people have observed, this is still a terrible way to compute the fibonacci numbers.
Here’s a solution in Java for serializing an XML tree. The iterative version uses a stack.
Output:
It appears there was a problem in the html code i pasted.
Here’s another attempt, this time escaping the angle brackets with backslashes.
Output:
Here’s another attempt, this time adding “sourcecode” markup.
SerializeIterative:
SerializeRecursive: