4

私はscalaコースをやっていて、与えられた例の1つは次のように定義されたsumInts関数です：

  def sumInts(a: Int, b: Int) : Int = 
    if(a > b) 0  
    else a + sumInts(a + 1 , b)

繰り返されるときにいくつかの値を出力することで、この関数をよりよく理解しようとしました：

class SumInts {
      def sumInts(a: Int, b: Int) : Int = 
        if(a > b) 0 else 
        {     
          println(a + " + sumInts("+(a + 1)+" , "+b+")")       
          val res1 = sumInts(a + 1 , b)
          val res2 = a
          val res3 = res1 + res2
          println("res1 is : "+res1+", res2 is "+res2+", res3 is "+res3)
          res3
        }
}

したがって、コード：

object SumIntsMain {

    def main(args: Array[String]) {

      println(new SumInts().sumInts(3 , 6));

  }

}

出力を返します：

3 + sumInts(4 , 6)
4 + sumInts(5 , 6)
5 + sumInts(6 , 6)
6 + sumInts(7 , 6)
res1 is : 0, res2 is 6, res3 is 6
res1 is : 6, res2 is 5, res3 is 11
res1 is : 11, res2 is 4, res3 is 15
res1 is : 15, res2 is 3, res3 is 18
18

誰かがこれらの値がどのように計算されるかを説明できますか？作成したすべての変数を出力してみましたが、まだ混乱しています。

4

3 に答える 3

6

manual-human-tracer on：

return sumInts(3, 6) | a = 3, b = 6
3 > 6 ? NO
return 3 + sumInts(3 + 1, 6) | a = 4, b = 6
4 > 6 ? NO
return 3 + (4 + sumInts(4 + 1, 6)) | a = 5, b = 6
5 > 6 ? NO
return 3 + (4 + (5 + sumInts(5 + 1, 6))) | a = 6, b = 6
6 > 6 ? NO
return 3 + (4 + (5 + (6 + sumInts(6 + 1, 6)))) | a = 7, b = 6
7 > 6 ? YEEEEES (return 0)
return 3 + (4 + (5 + (6 + 0))) = return 18.

手動-人間-トレーサーオフ。

于 2012-09-26T16:06:22.633 に答える
5

再帰コードの機能を理解するために、再帰ツリーを分析する必要はありません。実際、私はそれがしばしば単に混乱していると信じています。

それが機能するふりをする

私たちがやろうとしていることについて考えてみましょう。aある整数までのすべての整数を合計したいと思いbます。

a + sumInts（a + 1、b）

sumInts(a + 1, b)それが実際に私たちが望んでいることをしているふりをしましょう：からの整数を合計a + 1しますb。これを真実として受け入れるならば、私たちの関数がより大きな問題をから正しく処理することは非常に明白aですb。明らかに、合計から欠落しているのは、a単純に追加された追加の項だけだからです。正しく機能する必要があると結論付けています。

基礎：ベースケース

ただし、これsumInts()は何かに基づいて構築する必要があります。再帰が含まれない基本ケースです。

if（a> b）0

再帰呼び出しを詳しく見ると、特定の仮定が行われていることがわかります。aは、よりも低いと予想されますb。これは、合計が次のようになることを意味します a + (a + 1) + ... + (b - 1) + b。aがより大きい場合、bこの合計は自然に0と評価されます。

それが機能することを確認する

再帰呼び出しの保証では、これがsumInts()常にa1ずつ増加することを確認すると、実際には、ある時点で基本ケースに到達することになります。

さらに気付くと、それsumInts(b, b)は最終的に呼び出され、コードが機能することを確認できます。bはそれ自体より大きくないため、2番目のケースが呼び出されますb + sumInts(b + 1, b)。ここから、これが次のように評価されることは明らかですb + 0。これは、アルゴリズムがすべての値に対して正しく機能することを意味します。

于 2012-09-26T16:41:04.347 に答える
1

sumInts置換モデルについて言及したので、それをメソッドに適用してみましょう。

まず呼び出します（2番目の引数として6を使用しましたが、4を選択したので、入力量を減らすことができます）。したがって、の定義で3を3に、4を4にsumInts(3,4)置き換えましょう。これは私たちに与えます：absumInts

if(3 > 4) 0  
else 3 + sumInts(3 + 1, 4)

それで、これの結果はどうなるでしょうか？まあ、3 > 4明らかに誤りなので、最終結果はelse節に等しくなります。つまり、3にsumInts(4, 4)（4は3+1）の結果を加えたものになります。次に、結果がどうなるかを知る必要がありsumInts(4, 4)ます。そのために、もう一度置き換えることができます（今回はとを4に置き換えaますb）：

if(4 > 4) 0
else 4 + sumInts(4 + 1, 4)

さて、の結果はsumInts(4,4)4プラスの結果になりsumInts(5,4)ます。それで、何sumInts(5,4)ですか？代用者へ！

if(5 > 4) 0
else 5 + sumInts(5 + 1, 4)

今回はif条件が真なので、の結果は0です。これで、の結果は4でなければならないことがsumInts(5,4)わかりました。したがって、の結果は7である必要があります。sumInts(4,4)4 + 0sumInts(3,4)3 + 4

于 2012-09-26T16:04:07.937 に答える