Java再帰について

Question

以下のコードがどのような挙動をするかがわかりません。
漠然とした質問の仕方で恐縮ですが、回答頂けますと幸いです。

/**
     * 数値のリストから数式の全組み合わせを作成して、文字列のストリームで返す。
     * 例：[1, 2] -> ["1 +2", "1 -2", "12"]
     */
    static Stream<String> f(List<Integer> vals) {
        if (vals.size() == 1) {
        	return Stream.of(vals.get(0).toString());
        	}
        return Stream.of(" +", " -", "")
                .flatMap(op -> f(vals.subList(1, vals.size()))
                        .map(x -> vals.get(0).toString() + op + x)
                );
    }

Answer 1

static Stream<String> f(List<Integer> vals) {
        if (vals.size() == 1) {
            return Stream.of(vals.get(0).toString());
            }
        return Stream.of(" +", " -", "")
                .flatMap(op -> f(vals.subList(1, vals.size()))            
                        .map(x -> vals.get(0).toString() + op + x)
                );
    }
// f([2,3]) 再帰でもとの処理に戻る
// f([3]) 再帰でもと処理にもどる
// if (vals.size() == 1) の処理にはいり、3.toString()の処理をおこなう
// return Stream.of(" +", " -", "").flatMap(op -> f(vals.subList(1, vals.size()))
// f([3]) 再帰でもと処理にもどる
// この永遠のループで
// map(x -> vals.get(0).toString() + op + x)
// の処理に入れないような気がするのですが、どのタイミングでどうして
//  map(x -> vals.get(0).toString() + op + x)の処理にはいれるのでしょうか

Comments

[swordone]

永遠のループではないですよ．
f([2,3])の処理の中でf(vals.subList(1, vals.size())は"3"という文字列だけを持ったStream(streamAとします)を返します．(f([2,3]の中のf([3])が解決する)すると
f([2,3])の中のstreamA.map(x -> vals.get(0).toString() + op + x)の処理に入ります．
opはStream.of(" +", " -", "")で生成されるStreamから順番に，つまりこの括弧内の要素が順番に取り出されます．
"Stream("3")"の書き方が悪かったようです．申し訳ない．

[argius]

f([3])のときは、return Stream.of(vals.get(0).toString());でメソッドを抜けて return Stream.of(" +"...は評価されないので、永遠のループにはなりませんね。

[退会済みユーザー]

swordoneさん、argiusさん
ご回答ありがとうございます。
理解できた気がします。
ベストアンサーに処理の順を書いてみたのですが、理解があっているか、
お時間あります際に確認いただけますと幸いです。

Answer 2

概念的に説明しようとするとこうなるかと思います．
f([1,2,3])
→f([2,3]) :先頭の要素を抜いた配列を新たに渡す
→f([3])→Stream("3") :1つだけになったらStream化
→Stream(" +", " -", "").flatMap(op ->Stream("3").map(x -> "2" + op + x)
→"2",op(∈{" +", " -", ""}),x(∈{"3"})の順に要素を取って樹形図を書くように文字列決定
→Stream("2 +3", "2 -3", "23")
→Stream(" +", " -", "").flatMap(op ->Stream("2 +3", "2 -3", "23").map(x -> "1" + op + x)
→"1",op(∈{" +", " -", ""}),x(∈{"2 +3", "2 -3", "23"})
→"1 +2 +3", "1 +2 -3", "1 +23"; "1 -2 +3", "1 -2 -3", "1 -23";"12 +3", "12 -3", "123"

Comments

[退会済みユーザー]

swordoneさん
回答いただきまして、ありがとうございます。

理解できないポイントをベストアンサーに記載いたしました。
(ここだとコードでかけないようでみにくいのでベストアンサーに記しました。)
時間のある際にお答えいただけますと、幸いです。

Answer 3

分かりやすくするために、コードを一部変形しています。

fに[1, 2]が渡されたときの値と処理イメージだけコード内のコメントに記載しています。

static Stream<String> f(List<Integer> vals) {
    // vals = [1, 2]
    if (vals.size() == 1) {
        return Stream.of(vals.get(0).toString());
        // 今回の内容とは直接関係ありませんが
        // ここは return vals.stream().map(Object::toString);
        // のほうが良いと思います。
    }
    String head = vals.get(0).toString();
    // head = 1
    List<Integer> tail = vals.subList(1, vals.size());
    // tail = [2]
    return Stream.of(" +", " -", "").flatMap(op -> f(tail).map(x -> head + op + x));
    // [ " +", " -", "" ] をひとつずつopとして以下の処理を行う
    //   => tailに対して、ひとつずつxとして以下の処理を行う
    //     => tailはこの場合[2]だけなので、文字列 1 + op + 2 を生成
    // つまり
    //   " +" => "1 +2"
    //   " -" => "1 -2"
    //   ""   => "12"
    // を生成して、それをストリームで返す
}

考え方としては以上のようになります。
ただし、実際にストリームの処理が実行されるのは、collectやforEachのような終端処理を呼び出してからになります。そのため、一部変形した部分の処理順序は変わってしまいますが、意味と結果は同じになるはずです。

Comments

[退会済みユーザー]

argiusさん
回答いただきましてありがとうございます。

String head = vals.get(0).toString();
上記の時点ではvals=[1,2]であり、
if (vals.size() == 1) {
return Stream.of(vals.get(0).toString());
}
は適応されないようにおもうのですが、いかがでしょうか？

また、vals= [1,2,3]の場合で同じようになるのでしょうか？

[argius]

すみません、書き方が分かりづらかったですね。
おっしゃるとおり、vals=[1,2]のときはif (vals.size() == 1) { ... } は評価されません。
vals= [1,2,3]の場合はこれより少しだけ複雑になりますので、まずは一旦、この方式でご理解いただいたほうが良いと考えました。

[退会済みユーザー]

```lang-java
static Stream<String> f(List<Integer> vals) {
if (vals.size() == 1) {
return Stream.of(vals.get(0).toString());
}
return Stream.of(" +", " -", "")
.flatMap(op -> f(vals.subList(1, vals.size()))
.map(x -> vals.get(0).toString() + op + x)
);
}
// f([2,3]) 再帰でもとの処理に戻る
// f([3]) 再帰でもと処理にもどる
// if (vals.size() == 1) の処理にはいり、3.toString()の処理をおこなう
// return Stream.of(" +", " -", "").flatMap(op -> f(vals.subList(1, vals.size()))
// f([3]) 再帰でもと処理にもどる
// この永遠のループで
// map(x -> vals.get(0).toString() + op + x)
// の処理に入れないような気がするのですが、どのタイミングでどうして
// map(x -> vals.get(0).toString() + op + x)の処理にはいれるのでしょうか
```

[退会済みユーザー]

argiusさん
なんどもお答えいただきましてありがとうございます。
理解できないポイントをベストアンサーに記載いたしました。
(ここだとコードでかけないようでみにくいのでベストアンサーに記しました。)
時間のある際にお答えいただけますと、幸いです。