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, уменьшая предел на 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 один перед вызовом фактической рекурсивной процедуры, но это оставил упражнение для читателя.

Answer 2

Дайте n быть положительным числом и m является предшественником, m = n - 1.

Теперь предположим, что вы знаете, что (sum-divisibles m) имеет значение s. Как вы могли бы вычислить (sum-divisible n)?

Попробуйте написать функцию, которая принимает значение n и значение s, и вычисляет сумму для n.

(define (recur n s) ...) 

Тогда вы сможете определить sum-divisibles в терминах limit и рекурсивного применения sum-divisibles для limit - 1. Вам также необходимо позаботиться о базовом случае рекурсии, когда limit равен нулю.

Answer 3

Можно использовать 'под названием Let' рекурсии:

(define limit 1000) 

(let loop ((n 1)     ; starting values 
      (sum 0)) 
    (cond 
    [(> n limit) sum]   ; print out sum if limit reached; 

    [(or (= 0 (modulo n 3))  ; if n is divisible by 3 or 5 
     (= 0 (modulo n 5))) 
    (loop (add1 n) (+ sum n))] ; add this number to sum and loop again with next number 

    [else      ; if not divisible 
    (loop (add1 n) sum)]  ; loop with next number without adding to sum 
    ))