НОД - это решение итерационным?


Используя свойство, что НОД(А, B) = НОД(B, R), где Р является остатком, когда вы вычислить (а / б), можно написать рекурсивную функцию следующим образом:

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

Я тоже пытался написать следующее Как итеративную функцию, но она по-прежнему выглядит очень похоже на рекурсивное решение на мой взгляд. Это правильно, итерационное решение?

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

Редактировать: похоже, что первое решение было на самом деле многозвенным и в самом деле очень похож на решение написано в SICP (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html). Что бы рекурсивное решение этой проблемы выглядит?



1974
4
задан 29 марта 2011 в 05:03 Источник Поделиться
Комментарии
1 ответ

Действительно, обе версии у вас носят итеративный характер. На самом деле я не уверен, что рекурсивное решение имеет смысл в этом случае---как правило, рекурсивный подход к классической схеме проведения результаты работы по первому пункту, то рекурсией на остальные предметы. Вычисление НОД не вписывается в такую модель.

Одно маленькое предложение: вы можете использовать (ноль? б) вместо (= 0 б).

4
ответ дан 29 марта 2011 в 12:03 Источник Поделиться