I am trying to check if a number is prime using recursion. I was required to use a recursive helper function, but I am not sure how I should implement it.
I think I know the algorithm, but I've never tried to use a recursive helper function in Racket. This is my current thoughts:
i = 2
i = i + 1
i^2 <= n
continue.i
evenly divided n
, then it must be prime.This is what I have so far...
(define (is_prime n)
(if (<= n 1)
#f
(if (= (modulo n 2) 0)
#f
)
What would be a good approach using a recursive helper function??
Thanks!
Using a helper simply means that you should split your program in smaller parts, and possibly encapsulate loops with extra parameters in separate procedures - and in Scheme loops are frequently implemented via recursive calls. One (naïve) way to implement the is_prime
procedure would be:
(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))))
There are many ways to implement this procedure, and many possible optimizations; the above should be enough get you started.