GCD - is this solution iterative?

Question

Using the property that GCD(a, b) = GCD(b, r) where r is the remainder when you compute (a / b), you can write a recursive function as follows:

(define (gcd a b)
 ; recursive
 (if (= 0 b) a
 (gcd b (remainder a b))))

I also tried to write the following as an iterative function, but it still looks very similar to the recursive solution to my eye. Is this a correct, iterative solution?

(define (i-gcd a b)
 ; is this iterative?
 (i-gcd-iter (remainder a b) b))
(define (i-gcd-iter acc b)
 (if (= 0 b) acc
 (gcd b (remainder acc b))))

EDIT: It appears that the first solution was actually iterative, and in fact very similar to the solution written in SICP (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html). What would a recursive solution to this problem look like?

Answer 1

Indeed, both versions you have are iterative. I'm not actually sure that a recursive solution makes sense in this case---usually a recursive approach is for the classical pattern of holding the result of operating on the first item, then recursing into the remaining items. Calculating the GCD doesn't fit that pattern.

One small suggestion: you can use (zero? b) instead of (= 0 b).

• Michael K: How is the first solution not recursive? It calls itself until the problem is solved, the passes the result up the call stack until the caller is reached.
• C. K. Young: @Michael: In Scheme, tail recursion is treated as iteration (and indeed, in Scheme, that's the only way to do iteration; there is no goto facility). Therefore, Schemers treat tail recursion ("iteration") as a separate concept from non-tail recursion ("recursion").
• C. K. Young: (For readers unfamiliar with Scheme: all Scheme implementations are required to implement "proper tail calls", "tail call optimisation", or whatever you call it---again, because that's the only available method to implement iteration.)
• Michael K: So that (gcd) call essentially becomes (remainder), goto (if) ?
• C. K. Young: @Michael: Pretty much, yes.