回帰によるシリーズのラケット条件付き合計

Question

私はラケットを初めて使っています。私は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に達したときに停止するのと同じです。

再帰的な手順を書いてWENを覚えておくべき二つの重要な事柄があります。

1. 私たちはいくつかの点で停止していることを確認する必要があります - これはベースケースと呼ばれているが、この例では、元のループに1が含まれているため、0に達したときに発生します。我々はに持って
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 49) 
=> 543 

また、あなたが実際の再帰プロシージャを呼び出す前に1によって入力limitを下げるの世話をするヘルパープロシージャを記述できますが、それはです読者のための練習として残しました。

Answer 2

nは、正の数であり、mは、前身のm = n - 1です。

(sum-divisibles m)が値sに等しいことがわかったとします。 (sum-divisible n)を計算するにはどうすればよいですか？

nの値とsの値をとり、nの合計を計算してみてください。

(define (recur n s) ...) 

次に、あなたはlimitとlimit - 1ためsum-divisiblesの再帰的な適用に関してsum-divisiblesを定義することができるようになります。 limitが0の場合、再帰の基本ケースも処理する必要があります。

Answer 3

一つが使用できる再帰のために 'という名前は聞かせて'：

(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 
    ))