再帰関数は、理由を理解するのに苦労して和を返します。

Question

次の関数はレビューシートの上に私に与えられた：

(define mystery(lambda(m n) 
       (cond 
        ((= m 0) n) 
        ((= n 0) m) 
        (#t (+ 2(mystery(- m 1)(- n 1)))) 
        ))) 

最初の2つの条件は簡単です、それだけで私を混乱させています再帰otherwiseです。再帰は、両方がゼロに等しくなるまで繰り返されます。これは確かにその合計を返しません。誰か説明をすることはできますか？

Answer 1

私は最良の方法は、事前計算することではなく、入れ子にすることではないと感じます。我々はゼロのいずれかでテストベースケースを見て：

(mystery 0 2) ; ==> 2 
(nystery 3 0) ; ==> 3 

は、このように少なくとも一つの引数がゼロであるたびに、それは他の引数を返します。我々はベースケースは、常に私たちにはない、他の値を返します知っているので

(mystery 1 3)  ; == 
(+ 2 (mystery 0 2)) ; == (we switch known value) 
(+ 2 2)       
; ==> 4 

(mystery 4 1)  ; == (we substitute with the expression) 
(+ 2 (mystery 3 0)) ; == (we switch known value) 
(+ 2 3) 
; ==> 5 

：ゼロ以外の値で試してみて、あなたはちょうどその結果でそれを切り替える前に、我々はすでにやっている値を参照してください秒を覚えていますそれを事前に計算する必要があります。ここでは、それを行うことがあります：

(mystery 3 9)     ; == (we substitute with the expression) 
(+ 2 (mystery 2 8)    ; == (we substitute with the expression) 
(+ 2 (+ 2 (mystery 1 7)))  ; == (we substitute with the expression) 
(+ 2 (+ 2 (+ 2 (mystery 0 6))) ; == (we substitute with the expression, n, which is 6) 
(+ 2 (+ 2 (+ 2 6)))   ; == (we substitute (+ 2 6)) 
(+ 2 (+ 2 8))     ; == (we substitute (+ 2 8)) 
(+ 2 10)      ; == (we substitute (+ 2 10) 
; ==> 12 

私たちは一般化することができます。 nとmの最低値は、再帰がいつ終了するかを決定します。各ステップで2を加えて再帰します。

(define (double-min n m) 
(let ((vmin (min n m)) 
     (vmax (max n m))) 
    (+ (* 2 vmin) (- vmax vmin)))) 

再び2*m+(n-m) = m+m+(n-m) = m+n

Answer 2

まずは、何が起こっているか見るために少しより良いコードをフォーマットしてみましょう：今すぐ

(define (mystery m n) 
    (cond ((= m 0) n) 
     ((= n 0) m) 
     (else (+ 2 (mystery (- m 1) (- n 1)))))) 

、condは（上から下へ）trueである第一条件に対応するだけでアクションを実行することを覚えて、他は無視されます。いずれの条件もtrueでなければ、else部分が実行されます。重要なことは、実行されるアクションが1つだけであることです。特に

mまたはnのどちらかがゼロになったときに両方がゼロになったときに、あなたのmystery手順ではなく、停止します。 2つのうちの1つがゼロになると、再帰が巻き戻され、合計が返されます。実行をトレースするときは、これを見ることができます - 例えば、ラケットに：

(require racket/trace) 
(trace mystery) 
(mystery 3 2) 

>(mystery 3 2) 
> (mystery 2 1) 
> >(mystery 1 0) 
< <1 
< 3 
<5 

Answer 3

ただ、オスカル・ロペスの答えについては詳しく説明し（私はコメントでこれをフォーマットすることはできません）：私はそれがこれらを書くと便利だということを見つけます少し再帰数学関数の種類ダウン彼らは数学であるかのように：

がmをしようとn

• N + M = N m = 0の場合、自然数です。
• n + m = m（n = 0の場合）。
• n + m = n-1 + m-1 + 2;
• 他のケースはありません。

Answer 4

(define mystery(lambda(m n) 
       (cond 
        ((= m 0) n) 
        ((= n 0) m) 
        (#t (+ 2 (mystery (- m 1) (- n 1)))) 
        ))) 

第一および第二の条件は明らかにされ、その後、もしn > m以来、2つの数値を追加する空想方法を次のとおりです。したがって、それは作りの空想の方法です。

第ステートメントが動作する方法の説明：

1をそれぞれがMの取り出しnおよびこの関数外2として保持されます。 これは継続されるか、mは0又はnが0

Answer 5

になるまで第2のケースは明らかである、のいずれかの番号が0である2数の和が、他の数に等しいです。

最後に、引数が0であることを確認した後、両方が非0であることがわかりました。 その謎と仮定すると、その2つの引数の合計を返し、次いで

(+ 2 (mystery (- arg1 1) (- arg2 1))) 

は(mystery arg1 arg2)に等しく、引数の一つは、所望の結果を返す、0である場合、最終的に停止する合計を返します。

ミステリーが2つの引数の合計を返すと仮定すると、の再帰的な跳躍と呼ばれます。 （Googleそれ）