4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Michael K Mar 29 '11 at 14:02
  • \$\begingroup\$ @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"). \$\endgroup\$ – Chris Jester-Young Mar 29 '11 at 14:15
  • \$\begingroup\$ (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.) \$\endgroup\$ – Chris Jester-Young Mar 29 '11 at 14:17
  • \$\begingroup\$ So that (gcd) call essentially becomes (remainder), goto (if) ? \$\endgroup\$ – Michael K Mar 29 '11 at 14:18
  • \$\begingroup\$ @Michael: Pretty much, yes. \$\endgroup\$ – Chris Jester-Young Mar 29 '11 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.