1

有人可以解释一下以下函数如何递归工作。我可以理解更简单的递归示例，但我不明白如何(smooth n (- k 1))在此处的 or 语句下给出所需的值。

(define (divides a b)
  (= (modulo b a) 0))

(define (smooth n k)
  (and (>= k 2)
       (or (divides k n)
           (smooth n (- k 1)))))

(define (isprime p)
  (if (< p 2)
      #f
      (not (smooth p (floor (sqrt p))))))

我写了一个isprime不用1作素数的函数，但我仍然不太明白上述函数是如何工作的/它是如何与这个例子一起工作的。

4

3 回答 3

4

smooth如果我们改写如下，也许会更容易理解——它是一个完全等价的形式，但使用的是cond代替and, or：

(define (smooth n k)
  (cond ((< k 2)
         #f)
        ((divides k n)
         #t)
        (else
         (smooth n (- k 1)))))

基本上，该程序说明：

  • 如果k小于 2，则n不是“平滑”
  • 如果k准确划分n，n则为“平滑”
  • 否则，减去1并k继续尝试

换句话说：如果n除了它自己和 1 之外还有任何除数，我们说它是“平滑的”。显然，很容易编写一个程序来测试一个数是否为素数，就其“平滑度”而言 - 如果一个数字大于2且它不平滑（意思是：它除了自身和 之外没有除数，则它是素数1） . 这篇文章解释了为什么我们只需要测试一个数字的平方根的除数来确定它是否是素数。

于 2013-09-17T14:48:42.147 回答
1

如果您尝试写下每个呼叫，则更容易理解。例如：

(smooth 5 4)
    (smooth 5 3)
        (smooth 5 2)


(define (smooth 5 3)
   (and (>= 4 2)
        (or (divides 3 5)
            (smooth 5 (- 3 1)))))

(define (smooth 5 2)
   (and (>= 2 2)
        (or (divides 2 5)
            (smooth 5 (- 2 1)))))

(define (smooth 5 1)
   (and (>= 2 1) # This returns false
        #t))

(define (smooth 5 2)
   (and #f #t))

(define (smooth 5 3)
   (and #t #f))

(define (smooth 5 4)
   (and #t #f))

#f
于 2013-09-17T14:49:08.370 回答
1

smooth n k如果n在 2 和 之间有一个除数，则为真k。

它实际上相当于一个循环：

for i from k to 2 :
    if i divides n, return True
于 2013-09-17T14:52:24.150 回答