scheme - 递归序列的 Racket 条件和

Question

我是 Racket 的新手。我需要对所有小于 1000(或任何第 n 个值)的自然数求和，并且这些数字将被 3 或 5 整除。我有一个代码可以做到这一点，但使用迭代。但我必须通过递归做同样的事情。代码如下:

(define (sum-divisibles limit)
  (for/sum ([i (in-range 1 limit)]
            #:when (or (divides? i 3)
                       (divides? i 5)))
    i))

(define (divides? m n)
  (= 0 (remainder m n)))  

我需要做同样的事情，但使用递归而不是循环或迭代。

Answer 1

这很简单，只要您将循环中的每次迭代可视化为函数调用即可。想一想:原来for循环来自 1直至并包括 limit-1 .这与从 limit-1 开始相同, 将限制减少 1在每次函数调用时，当我们到达 0 时停止.

在编写递归过程时要记住两件重要的事情:

1. 我们必须确保我们在某个点停下来 - 这称为基本情况；对于这个例子，当我们到达 0 时就会发生这种情况(因为原始循环包括 1 )。
2. 我们必须合并我们在调用递归时获得的部分结果:如果当前数字恰好可以被3整除或 5然后我们将它添加到其余的递归调用中，否则我们将忽略它但无论如何都会继续推进递归，直到我们达到基本情况。

这就是我的意思:

(define (sum-divisibles limit)
  (cond ((= limit 0) 0)                             ; base case, stop recursion
        ((or (divides? limit 3) (divides? limit 5)) ; does the condition hold?
         (+ limit                                   ; then we add current value
            (sum-divisibles (- limit 1))))          ; and advance the recursion
        (else                                       ; otherwise skip it
         (sum-divisibles (- limit 1)))))            ; and advance the recursion

注意首字母 limit值，请记住在您的原始代码中 limit 没有加到和中(迭代在到达它之前停止)，因此调用递归版本的等效方法是这样的:

(sum-divisibles (- n 1))

例如获取与(sum-divisibles 50)相同的值使用您的代码，我们必须在递归版本中这样调用它:

(sum-divisibles 49)
=> 543

或者，您可以编写一个帮助程序来减少输入 limit在调用实际的递归过程之前通过一个，但这留给读者作为练习。