我想,以检查是否使用递归的数是素数。我需要使用递归辅助函数,但我不知道我应该如何实现它。
我想我知道的算法,但我从来没有尝试过的球拍使用递归辅助函数。这是我目前的想法:
i = 2
i = i + 1
i^2 <= n
继续。i
值平分秋色n
,那么它必须是素数。这是我迄今为止...
(define (is_prime n)
(if (<= n 1)
#f
(if (= (modulo n 2) 0)
#f
)
什么是使用递归辅助函数的好办法?
谢谢!
使用辅助仅仅意味着你应该在更小的部分分割你的程序,并可能封装在单独的程序额外的参数的循环 - 在循环方案通过递归调用频繁执行。一(天真)的方式来实施is_prime
程序是:
(define (is_prime n)
(cond ((<= n 1) #f)
((= n 2) #t)
((= (modulo n 2) 0) #f)
(else (check 3 n))))
; recursive helper
(define (check i n)
(cond ((> (* i i) n) #t)
((= (modulo n i) 0) #f)
(else (check (+ i 2) n))))
有实现这个过程中,许多可能的优化方法很多;以上应该足够让你开始。
(define (isPrimeHelper x k)
(if (= x k) #t
(if (= (remainder x k) 0) #f
(isPrimeHelper x (+ k 1)))))
(define ( isPrime x )
(cond
(( = x 0 ) #f)
(( = x 1 ) #f)
(( = x 2 ) #t)
( else (isPrimeHelper x 2 ) )))
我喜欢这个版本。