Scheme Recursive Function

Question

Can someone give me an explanation as to how the following function works recursively. I can understand simpler recursive examples, but I don't understand how (smooth n (- k 1)) gives the value desired under the or statement here.

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

I wrote an isprime function that doesn't use 1 as a prime number, but I still don't quite understand how the above function works/how it works with this example.

This isn't properly formatted or runnable code. This case is fairly simple, but could you adjust it for everyone's convenience, and especially so that if new users find this question it can be useful to them, too. — Joshua Taylor, Sep 17 '13 at 14:53
`smooth n k = Exists i In (k,k-1,...,2) SuchThat (n%i==0)`. `isprime p = p>=2 && not (smooth p [sqrt p])`. The name choice is unfortunate: [smooth numbers](https://en.wikipedia.org/wiki/Smooth_number) are something else. The reverse testing order is better - numbers are more likely to have smaller factors than bigger factors. — Will Ness, Sep 19 '13 at 16:17

score 4 · Accepted Answer · edited May 23 '17 at 12:05

Perhaps it'll be easier to understand if we rewrite smooth as follows - it's a completely equivalent form, but makes use of cond instead of and, or:

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

Basically, the procedure is stating that:

if k is less than 2, then n is not "smooth"
if k divides exactly n, then n is "smooth"
otherwise, subtract 1 from k and keep trying

In other words: if n has any divisor besides itself and 1, we say it's "smooth". Clearly, it's easy to write a procedure that tests if a number is prime, in terms of its "smoothness" - a number is prime if it's greater than 2 and it's not smooth (meaning: it doesn't have a divisor besides itself and 1). And this post explains why we only have to test the divisors up to the square root of a number to determine if it's prime.

score 1 · Answer 2 · answered Sep 17 '13 at 14:49

It is easier to understand if you try to write down each call. For example:

(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

score 1 · Answer 3 · answered Sep 17 '13 at 14:52

1

smooth n k is true if n has a divisor between 2 and k.

It is just equivalent to a loop actually :

for i from k to 2 :
    if i divides n, return True

answered Sep 17 '13 at 14:52

Lithy

817
12
23

Scheme Recursive Function

3 Answers3