Рекурсивная функция схемы

Question

Может кто-нибудь дать мне объяснение, как следующая функция работает рекурсивно. Я могу понять более простые рекурсивные примеры, но я не понимаю, как (smooth n (- k 1)) дает значение, которое требуется в инструкции или здесь.

(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 как простое число, но я до сих пор не совсем понимаю, как данная функция работает/как он работает с этим примером.

Answer 1

Возможно, это будет легче понять, если переписать 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). И это post объясняет, почему нам нужно только проверять дивизоры до квадратного корня числа, чтобы определить, является ли оно простым.

Answer 2

Это легче понять, если вы попытаетесь записать каждый звонок. Например:

(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 

Answer 3

smooth n k верно, если n имеет делитель между 2 и k.

Это просто эквивалентно петле на самом деле:

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