質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.50%

Java再帰について

受付中

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,355
退会済みユーザー

退会済みユーザー

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


/**
     * 数値のリストから数式の全組み合わせを作成して、文字列のストリームで返す。
     * 例:[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)
                );
    }
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

0

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

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"
    // を生成して、それをストリームで返す
}


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/20 19:00

    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]の場合で同じようになるのでしょうか?

    キャンセル

  • 2015/06/20 19:06

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

    キャンセル

  • 2015/06/21 12:14

    ```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)の処理にはいれるのでしょうか
    ```

    キャンセル

  • 2015/06/21 12:16

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

    キャンセル

0

概念的に説明しようとするとこうなるかと思います.
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"

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 12:18

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

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

    キャンセル

0

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)の処理にはいれるのでしょうか

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 12:43

    永遠のループではないですよ.
    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")"の書き方が悪かったようです.申し訳ない.

    キャンセル

  • 2015/06/21 12:45

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

    キャンセル

  • 2015/06/21 13:13

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る