scalaでの部分和問題の内部の動きが分からない

Question

ある教材でscalaを使い部分和を勉強しているのですが、教材のコードにprintlnを書き足して途中の値を追っても動きが理解出来ません。

object PartialSumDFS extends App {
  val a = Seq(3, 6, -5, 7)
  val n = a.length
  val k = 8

  def isMatchAndResult(index: Int,partial: Seq[Int]): (Boolean,Seq[Int]) ={
    println(s"① index:${index} partial:${partial}")
    if (index == n){
      return if (partial.sum == k)(true,partial) else (false, Seq())
    }

    val (isMatchNotAdd, resultNotAdd) = isMatchAndResult(index + 1, partial)
    if (isMatchNotAdd) return (isMatchNotAdd,resultNotAdd)

    println(s"② index:${index} partial:${partial}")

    isMatchAndResult(index + 1, partial :+ a(index))
  }
  val(isMatch,result) = isMatchAndResult(0,Seq())
  if(isMatch) println(s"Yes ${result}") else println("No")
}

これが教材のコード（printlnは自分で追加）で、実行したら

① index:0 partial:List()
① index:1 partial:List()
① index:2 partial:List()
① index:3 partial:List()
① index:4 partial:List()
② index:3 partial:List()
① index:4 partial:List(7)
② index:2 partial:List()
① index:3 partial:List(-5)
① index:4 partial:List(-5)
② index:3 partial:List(-5)
① index:4 partial:List(-5, 7)
② index:1 partial:List()
① index:2 partial:List(6)
① index:3 partial:List(6)
① index:4 partial:List(6)
② index:3 partial:List(6)
① index:4 partial:List(6, 7)
② index:2 partial:List(6)
① index:3 partial:List(6, -5)
① index:4 partial:List(6, -5)
② index:3 partial:List(6, -5)
① index:4 partial:List(6, -5, 7)
Yes List(6, -5, 7)

という結果が返ってきました。上から5行目まではindexが３になるまで再帰関数がisMatchAndResult(index + 1, partial)により繰り返し呼び出されたためで、6-7行目はindexが3のときのisMatchAndResult(index + 1, partial)の結果がfalseになったので後続のコードが引き続き実行された結果とわかるのですが、8行目でindexに２が代入されている理由がわかりません。
index=2となるような計算式が見当たらないのですが、どこからきたのでしょうか…。

Comments

[rysh]

そもそも何をやろうとしているプログラムなのかわからないのでその部分の説明が欲しいです。

Answer 1

8行目の"② index:2 ~"の表示は3行目の"① index:2 ~"の続きです

身もふたもないことを言ってしまえば一行ずつ実行していけばわかることではあるんですが、おそらく混乱のもとになってるのは、一つ目のprintlnが呼び出されたindexを表示するのに対して、二つ目のprintlnが呼び出し元のindexを表示してることです。
二つ目のprintlnを消すか、もっと別の内容を表示するように変えたほうが理解しやすいんじゃないでしょうか

一つ目のprintlnに字下げを追加して表示

index:0 partial:List()
  index:1 partial:List()
    index:2 partial:List()
      index:3 partial:List()
        index:4 partial:List()
        index:4 partial:List(7)
      index:3 partial:List(-5)
        index:4 partial:List(-5)
        index:4 partial:List(-5, 7)
    index:2 partial:List(6)
      index:3 partial:List(6)
        index:4 partial:List(6)
        index:4 partial:List(6, 7)
      index:3 partial:List(6, -5)
        index:4 partial:List(6, -5)
        index:4 partial:List(6, -5, 7)
Yes List(6, -5, 7)