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

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

ただいまの
回答率

91.06%

  • Java

    11779questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

再帰的メソッドの変数の遷移を解説して欲しいです

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 126

gyro16

score 77

前提・実現したいこと

このプログラムのrecur3(3)で実行したときの
do-while文でのswの遷移が掴めません。
特にdo-while文でswが2になるタイミングが分かりません。
解説してもらえる方お願いします。

do-while文内の
sw = sstk[ptr] + 1
この部分です。

sw == 2になる機序が分かりません。

やっていることは
public void recur3(int n){
recur3(n-1);
recur3(n-2);
System.out.println(n);
}

do-while文で
ptr--をやっているので
n = nstk[ptr] が範囲外IndexOutOfBoundsExceptionにならないかと思うんですが、
実行するとならない。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

import java.util.Scanner;

class Recur3 {

   static void recur3(int n) {
      int[] nstk = new int[100];
      int[] sstk = new int[100];
      int ptr = -1;
      int sw = 0;

      while (true) {
         if (n > 0) {
            ptr++;
            nstk[ptr] = n;
            sstk[ptr] = sw;

            if (sw == 0)
               n = n - 1;
            else if (sw == 1) {
               n = n - 2;
               sw = 0;
            }
            continue;
         }
         do {
            n  = nstk[ptr];
            sw = sstk[ptr] + 1;
        ptr--;

            if (sw == 2) {
               System.out.println(n);
               if (ptr < 0)
                  return;
            }
         } while (sw == 2);
      }
   }

   public static void main(String[] args) {
      Scanner stdIn = new Scanner(System.in);

      System.out.print("整数を入力せよ:");
      int   x = stdIn.nextInt();

      recur3(x);
   }
}

試したこと

nstk[0] 3 nstk[1] 2 nstk[2] 1
sstk[0] 0 sstk[1] 0 sstk[2] 0

n = nstk[2] = 1
sw = sstk[2] + 1 = 0 + 1 = 1
ptr-- =2 - 1 = 1
sstk[0] 0 sstk[1] 0 sstk[2] 0
n = nstk[1] = 2
sw = sstk[1] + 1 = 1??

補足情報(言語/FW/ツール等のバージョンなど)

より詳細な情報

  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

checkベストアンサー

+1

メソッドで渡された引数nをメソッド内で書き換えているという恐ろしいソースコードですが。
IDE(eclipse)を使ってデバック実行でブレイクポイントを起きながらステップ実行して変数の値を折ってみると理解しやすいかと。

以下はデバックプリントを追加したソースコードです、ご参考まで。

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Recur3 {
    static void recur3(int n) {
        // new int[100]で宣言する意味はないです。
        int[] nstk = new int[n];
        int[] sstk = new int[n];
        int ptr = -1;
        int sw = 0;

        while (true) {
            if (n > 0) {
                ptr++;
                nstk[ptr] = n;
                sstk[ptr] = sw;
                if (sw == 0)
                    n -= 1;// n = n - 1;
                else if (sw == 1) {
                    n -= 2;
                    sw = 0;
                }
                continue;
            }
            do {
                n  = nstk[ptr];
                sw = sstk[ptr] + 1;
                System.out.println(Stream.generate(() -> "-").limit(30).collect(Collectors.joining("")));
                System.out.println(ptr);
                System.out.println(Arrays.toString(nstk) + ' ' + Arrays.toString(sstk));
                ptr--;
                if (sw == 2) {
                    System.out.println(n);
                    if (ptr < 0)
                        return;
                }
            } while (sw == 2);
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.print("整数を入力せよ:");
        int x = stdIn.nextInt();
        recur3(x);
    }

}

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/12/30 16:20

    ステップ実行でのデバックのやり方を覚えました。参考になりました。
    while文の解釈を先入観で見違えていました。
    それにしても仮引数を書き換えるなんて良くないですね。
    テキストの解答コードが元なので自作ではありません。
    再帰的なものを非再帰的に実現するという非合理な問題ですので、作者のセンスが…ということです

    キャンセル

+1

再帰呼び出しで知っておくべきことは「引数・ローカル変数は呼出しごとに別々の変数の場所が割り当てられる」という点だと思います。

int factorial(int n) {
  int[] dummy = new int[] { n }; // 意味がないが例のために宣言した
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}


int result = factorial(1);
  -> factorial(1)の呼び出し
       引数:n = 1                   // 変数#1
       変数:dummy = [ 1 ]           // 変数#2
         -> factorial(0)の呼び出し
              引数:n = 0            // 変数#3
              変数:dummy = [ 0 ]    // 変数#4


上のコメントの「変数#数字」は変数の場所を表すと考えてください。
上記でfactorial(1)の呼び出し時のn, dummyの変数の場所は変数#1, #2になりますが、factorial(0)の呼び出し時には別の場所#3, #4に記録されます。引数やローカル変数はどの呼び出し中に参照されたかでどの場所の値がアクセスされるかが決まります。

再帰呼び出しでの変数の値に混乱するという場合はこうした意味について把握しておくと混乱を避けられると思います。

このような回答をした理由は、質問者さんの引っかかっている点が

int[] nstk = new int[100];
int[] sstk = new int[100];

これらの配列が各再帰呼び出しにおいて同一のものが参照されるといった勘違いをされているせいではないかと思ったためです。

もしそういう勘違いをしておられないのなら本回答は参考にならないと思います。その場合はおそらく関数内での変数の推移について何かの勘違いをしておられるのが原因であって、再帰呼び出しかどうかとは関係しない問題のように思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

  • 受付中

    JAVAに関する質問

    JAVAに関する質問です。 JAVAで以下のプログラムを作成しました。 import java.util.Scanner;  public class Sample {  /

  • 受付中

    java 進数変換 プログラム

    前提・実現したいこと ここに質問したいことを詳細に書いてください (例)PHP(CakePHP)で●●なシステムを作っています。   ■■な機能を実装中に以下のエラーメッ

  • 解決済

    入力した値を表示させない方法

    初めまして。現在JAVAを学んでいる初心者です。 現在、配列に格納している値を表示させるプログラムを作っています。 ユーザーから入力があった場合、次に配列の値を表示させるとき、

  • 解決済

    じゃんけん3回先勝

    じゃんけんで先に3回買った方が勝ちというプログラムを書いていますが、実行すると勝ち数が0になり、じゃんけんすら行われずに終了してしまいます。 どうすれば良いのでしょうか・・・

  • 解決済

    javaの演算子に関する質問です。

    キーボードから読み込んだ整数値に10を加えた値と,10減らした数を表示するプログラムを作っています。一応プログラムは完成したのですがコンパイルエラーになります。なぜでしょうか??プ

  • 解決済

    javaで作れる学習プログラムってどのようなものが作れますか

    意図 javaを使って学習プログラムを作成してほしいといわれました。 しかし、イメージがわきません。 どんなものが作れるのでしょうか

  • 解決済

    javaの配列に文字を格納して処理する方法

     疑問、質問 javaについての質問です。 キーボードから文字を一字ずつ入力し配列に格納する。 その後配列に格納されていた文字によってそれぞれ順番に処理していくというプログラ

  • 解決済

    Javaです。入力した数字が与えられた複数の数字の何番目に来るのか表示したいです。

    前提・実現したいこと Javaを勉強し始めたばかりで、まだ右も左も分かりません。 入力した数字(例:18)が与えられた複数の数字(例:0 10 15 20 25)の何番目に来る

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

  • Java

    11779questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。