使用递归辅助函数检查素数 [英] Check for a prime number using recursive helper function

问题描述

我正在尝试使用递归检查数字是否为素数.我被要求使用递归辅助函数，但我不确定应该如何实现它.

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.

我想我知道算法，但我从未尝试过在 Racket 中使用递归辅助函数.这是我目前的想法:

I think I know the algorithm, but I've never tried to use a recursive helper function in Racket. This is my current thoughts:

1. 看看 n 是否可以被 i = 2
整除
2. 设置 i = i + 1
3. 如果 i^2 <= n 继续.
4. 如果没有 i 的值被 n 等分，那么它一定是质数.

1. See if n is divisible by i = 2
2. Set i = i + 1
3. If i^2 <= n continue.
4. If no values of 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??

谢谢！

推荐答案

使用 helper 仅仅意味着你应该将你的程序分成更小的部分，并可能在单独的过程中封装带有额外参数的循环——并且在 Scheme 中经常实现循环通过递归调用.实现 is_prime 过程的一种(幼稚)方法是:

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.

这篇关于使用递归辅助函数检查素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！