スカラ：リストの再帰的集計

Question

def sum(xs: List[Int]): Int = { 
    if(xs.isEmpty) 
    0 
    else 
    xs.head + sum(xs.tail) 
} 

最後の行は誰でも説明できますか？

中間結果は に保存されます。xs.head + sum（xs.tail） と、その後に追加する要素が1つありますか？

Answer 1

再帰IMHOを説明する最善の方法は、段階的に進み、実際に何が起こっているかを見ることです。もう一つ役立つのは、return文を追加することです。特に、Javaのような言語から来た場合は、何が起こっているのかが分かりやすいためです。あなたのケースでは

def sum(xs: List[Int]): Int = { 
    if(xs.isEmpty) 
    return 0 
    else 
    return xs.head + sum(xs.tail) 
} 

リスト内のすべての整数を合計する機能を持っている：リターンと

あなたの関数は次のようになります。

だから、どのように振る舞うが機能します以下の値（1,2,3）

でリストを使用して、関数と呼ばれていることを想像することができますか？

まず、関数呼び出しは次のようになります。

if(xs.isEmpty) // false - it has 3 elements (1,2,3) 
    return 0 // skipped 
else 
    return 1 + sum((2,3)) // xs.head is changed with 1 and xs.tail is list with (2,3) 

第二コールリスト（2,3）となりました：

if(xs.isEmpty) // false - it has 2 elements (2,3) 
    return 0 // skipped 
else 
    return 2 + sum((3)) // xs.head is changed with 2 and xs.tail is list with (3) 

Trirdコールは、（3）リストを以下のようになります。

if(xs.isEmpty) // false - it has 1 elements (3) 
    return 0 // skipped 
else 
    return 3 + sum(()) // xs.head is changed with 3 and xs.tail is empty list now 

4回目の呼び出しは空のリストです：

if(xs.isEmpty) // true 
    return 0 // Recursion termination case triggered 

は、だから今、私たちはこのような何か探して私たちの和コールスタックがあります。

sum((1,2,3)) 
    where sum = 1 + sum((2,3)) 
     where sum = 2 + sum((3)) 
      where sum = 3 + sum(())  
      where sum = 0 

をそして、我々は単に値を返す開始：

sum((1,2,3)) 
     where sum = 1 + 5 
      where sum = 2 + 3 
       where sum = 3 + 0 

は、私たちは1,2（（合計で終わります、3））= 6

その理由は、「中間結果」を格納する必要がないのは、合計の計算が最後から始まり、後ろに向かって移動するためです。

Answer 2

実際の例について考えてみると役に立ちます。我々が持っていたとしましょう：

List(1,3,5) 

は（リストが空でない）最初のテストは失敗しsum方法、これを渡します。次に、尾部のsumに先頭項目、つまりsum(List(3,5))を追加します。したがって、2番目の式が計算されるまで、操作は完了することができず、sumが2回呼び出されます。最初のテストは失敗し（List(3,5)は空ではありません）、このメソッドは3 + sum(List(5))の値を返します。再び2番目の式を計算するまでは完了できないので、sumが再び呼び出されます。再び、List(5)が空ではないため、最初のテストは失敗し、この呼び出しは5 + sum(List())の値を返します。最後の時間のために、sumはそう、と呼ばれ、この時間は、最初のテストは成功し、0を返します：

sum(List()) = 0 
sum(List(5)) = 5 
sum(List(3,5)) = 8 
sum(List(1,3,5)) = 9 

は、この種のものを考え出す再帰を理解するのに役立つ（必須）です。

Answer 3

中間結果（xs.headおよびsum（xs.tail））は、スレッドのJavaスタックを実行するメモリ領域であるフレームに格納されます。 sum関数のネスト呼び出しごとに別々のフレームが作成され、その結果がsum呼び出しごとに分離されます。 Java documentationから

：

フレームは、データおよび部分的な結果を格納するために、ならびに動的リンクを実行するために、メソッドの値を返し、ディスパッチ例外用いられます。

メソッドが呼び出されるたびに新しいフレームが作成されます。フレームは、そのメソッドの呼び出しが完了すると、その完了が正常であるか突然であるか（キャッチされない例外をスローする）のいずれであっても、破棄されます。フレームは、フレームを作成しているスレッドのJava Virtual Machineスタック（§2.5.2）から割り当てられます。各フレームには、ローカル変数（§2.6.1）、それ自身のオペランドスタック（§2.6.2）、および現在のメソッドのクラスの実行時定数プール（§2.5.5）への参照があります。 。ここで

は、あなたのコードは、JVMバイトコードにコンパイルする方法です：

public int sum(scala.collection.immutable.List<java.lang.Object>); 
    Code: 
     0: aload_1 
     1: invokevirtual #63     // Method scala/collection/immutable/List.isEmpty:()Z 
     4: ifeq   11 
     7: iconst_0 
     8: goto   30 
     11: aload_1 
     12: invokevirtual #67     // Method scala/collection/immutable/List.head:()Ljava/lang/Object; 
     15: invokestatic #73     // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I 
     18: aload_0 
     19: aload_1 
     20: invokevirtual #76     // Method scala/collection/immutable/List.tail:()Ljava/lang/Object; 
     23: checkcast  #59     // class scala/collection/immutable/List 
     26: invokevirtual #78     // Method sum:(Lscala/collection/immutable/List;)I 
     29: iadd 
     30: ireturn 

注終わり近くIADD命令。命令をIADD のdescriptionから：

value1とvalue2の両方がint型である必要があります。 値はオペランドスタックからポップされます。 intの結果はvalue1 + value2です。結果はオペランドスタックにプッシュされます。