再帰的なメソッドをスタックを使って非再帰的に書くには？

Question

###前提・実現したいこと
IntStackはInt型のスタック、先入れ後出しのStackです。

static void recur3(int n){
if(n > 0){
recur3(n-1);
recur3(n-2);
System.out.println(n);
}
これをIntStackをつかって

static void recur3(int n){
IntStack s = new IntStack(100);
if(n > 0){
s.push(n);
n = n - 2;
}
continue;
if(s.isEmpty() != true){
n = s.pop();
System.out.println(n);
}
}

これだと
static void recur3(int n){
if(n > 0){
recur3(n-2);
System.out.println(n);
}
}
しかなりません

IntStackをつかって書くにはどうすれば良いでしょうか？
recur(n-1)まで含めて書くにはどうすれば良いでしょうか？

スタック　入り口　1, 2, 1, 3 底

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

static void recur3(int n){
 if(n > 0){
  recur3(n-1);
  recur3(n-2);
  System.out.println(n);
}

###該当のソースコード

static void recur3(int n){
 IntStack s = new IntStack(100);
 if(n > 0){
  s.push(n);
  n = n - 2;
 }
 continue;
 if(s.isEmpty() != true){
  n = s.pop();
  System.out.println(n);
 }
}

static void recur3(int n){
	int nn = n;
	IntStack s = new IntStack(100);
	if(n > 0){
		s.push(n);
		n = n - 2;
	}
	continue;
	if(nn > 0)
		nn = nn - 1;
		s.push(nn);
	}
	continue;
	if(s.isEmpty() != true){
		n = s.pop();
		System.out.println(n);
	}
}

###試したこと
recur3(1)→ recur3(0) recur3(-1) Sys.out.1 → Sys.out.1
recur3(2)→ recur3(1) recur3(0) Sys.out.2 → Sys.out.1 Sys.out.2
recur3(3)→ recur3(2) recur(1) Sys.out.3 → Sys.out.1 Sys.out.2 Sys.out.1 Sys.out.3

スタック　入り口　1, 2, 1, 3 底

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

Comments

[anndonut]

ちなみに「該当のソースコード」にはrecur3メソッドが２つ書いてありますね。２つのコードを試したけど両方ダメだったという意味でしょうか？

Answer 1

Deque<Integer>を使った書き方です。「Forthの力を信じよ！」ってやつです。

import java.util.Deque;
import java.util.ArrayDeque;

public class Main {
    public static final int RECURSION = 0;
    public static final int PRINT = 1;
    
    public static void recur3(int n) {
        // Javaのドキュメントによると、Stackクラスの代わりに
        // Dequeインターフェースを使用することが推奨されています。
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(n);
        stack.push(RECURSION);
        while (!stack.isEmpty()) {
            if (stack.pop() == RECURSION) {
                int num = stack.pop();
                if (num > 0) {
                    stack.push(num);
                    stack.push(PRINT);
                    stack.push(num - 2);
                    stack.push(RECURSION);
                    stack.push(num - 1);
                    stack.push(RECURSION);
                }
            } else { // stack.pop() == PRINT
                System.out.println(stack.pop());
            }
        }
    }
    
    public static void main(String[] args) {
        recur3(3);
    }
}

Comments

[anndonut]

このコードを解説するために、デバッグ用の出力を追加したものを用意しました。
https://gist.github.com/haruo-wakakusa/db9ce844370f4359effa49f992fb810e
まず、recur3(1)について出力してみましょう。

[0, 1]
[0, 0, 0, -1, 1, 1]
[0, -1, 1, 1]
[1, 1]
1
[]

こうなります。Dequeでpush, popを行うと、データの末尾ではなく先頭にデータが追加・削除されるようですね。これを、Forth風（ただしForthとは逆の書き方）に書くと、こうなります。

R 1
R 0 R -1 P 1
R -1 P 1
P 1
1が出力
スタックが空になり、終了。

つまり、Rがrecur3メソッドで、PがSystem.out.printlnメソッドに対応する命令です。Forthでは命令と引数を同じ型で表現しても正しく動作するので、R=0, P=1としています。

recur3(1)の開始時には、R 1という命令を置いています。これは分かりやすいですね。
次の行では、R 1の引数である1が0より大きいので、R 0 R -1に展開されます。
その次の行では、R 0が先頭に来ていますが、Rの引数が0なので、0より大きくなく、そのまま消費されます。
その次の行では、R -1が先頭に来ていますが、Rの引数が-1なので、0より大きくなく、そのまま消費されます。
その次の行では、P 1が先頭に来ていますが、Pはその引数を表示するので、1を表示します。
この時点で、スタックが空になったので、プログラムを終了します。

recur3(2)以降についても同様のことが言えます。分からなければさらに解説させて頂きます。

[gyro16]

分かりました。分かりやすいです。
Dequeでもpushやpopできるんですね。

Answer 2

import java.util.Scanner;
public class En5_5b{
	static void recur3(int n) throws IntStack.OverflowIntStackException, IntStack.EmptyIntStackException{
		int num = n;
		IntStack s = new IntStack(100);
		while(n > 0){
			try{
				s.push(n);
			}catch(IntStack.OverflowIntStackException e){
				System.out.println("スタックが満杯です。");
			}
			n -= 2;
		}
		while(num-1 > 0){
			try{
				s.push(num-1);
			}catch(IntStack.OverflowIntStackException e){
				System.out.println("スタックが満杯です。");
			}
			num--;
		}
		while(s.isEmpty() != true){
			try{
				n = s.pop();
			}catch(IntStack.EmptyIntStackException e){
				System.out.println("スタックが空です。");
			}
			System.out.println(n);
		}
	}
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		System.out.println("整数を入力せよ：");
		int n = stdIn.nextInt();
		recur3(n);
	}
}

Comments

[anndonut]

gyro16さんのコードはn=4のときに1 2 3 2 4と出力しませんか？貪欲法で解きに行ってこけてるように思われたので。

Answer 3

分かりづらいけどこんな感じです。もっと分かりやすい回答があったらそっちに習ったほうがいいかもしれませんね。IntStackは使ってないです。Stackクラスを使ってます。

import java.util.Stack;

public class Main {
    public class Recur3 {
        private int num = 0;
        private Stack<Recur3> s = null;
        
        public Recur3(int n, Stack<Recur3> stack) {
            num = n;
            s = stack;
        }
        
        public void run() {
            if (num > 0) {
                s.push(new Printer(num, s));
                s.push(new Recur3(num-2, s));
                s.push(new Recur3(num-1, s));
            }
        }
    }
    
    public class Printer extends Recur3 {
        private int num = 0;
        
        public Printer(int n, Stack<Recur3> stack) {
            super(n, stack);
            num = n;
        }
        
        public void run() {
            System.out.println(num);
        }
    }
    
    private Recur3 create(int n, Stack<Recur3> stack) {
        return new Recur3(n, stack);
    }
    
    public static void main(String[] args) {
        Stack<Recur3> s = new Stack<Recur3>();
        s.push((new Main()).create(4, s));
        while (!s.empty()) {
            s.pop().run();
        }
    }
}

Comments

[gyro16]

ロジック違いませんか？結果違うと思いますよ
ただ並列で並べただけでは再帰的な結果とは違いますよ

[anndonut]

Javaの内部クラスが分かって、しかもForthという言語が分かるなら僕のやってることが分かると思う。

[gyro16]

recur3(3)は1 2 1 3ですから、答えが違いますよ。
recur3(4)でもrecur3(3) recur3(2) Sys.out.4
ですから1 2 1 3 1 2 4ですから結果が違いますよ。

[anndonut]

gyro16さん、ご指摘ありがとうございます。ケアレスミスでした。コード直しておきます。

[gyro16]

箱型に箱型を押し込む。それを再帰的に繰り返すスタックですか。

[anndonut]

IntStackクラスは本の中に登場するものだと思いますが、一般的にはjava.util.Stackクラスを使います。ただ、Stackクラスは総称型(ジェネリクス)で、型引数を必要とします。型引数にはintなどのプリミティブ型を指定することはできません。ただ、int型のラッパーであるInteger型を型引数にとることができ、IntStackクラスと同様の使い方ができます。Forthはoperatorとargumentを逆順で並べる言語ですが、逆順で並べるとスタックの構造と相性がいいのでそうします。詳しくは私のもう一つのコードをご参照ください。

[swordone]

Stackは古いので、Dequeで宣言してLinkedListやArrayDequeを使うべき。

[anndonut]

Stackは古いかもしれないけど、Stackを使わないとForthを実装してる感が出ないんじゃない？Dequeを使う場合は、「これはスタックとして使っています」と、コメントを添えるべき。あと、できることなら代替コードを示して、具体的に、速度的に優れているとか、サイズが大きくなるとオーダー的に優れているとか示してあげると親切だと思います。

[swordone]

速度などの問題ではなく、Stackのドキュメントに記載されている事です。
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html
> より完全で一貫性のある一連のLIFOスタック・オペレーションが、Dequeインタフェースとその実装によって提供されています。このクラスよりもそれらを優先的に使用するようにしてください。

[anndonut]

それは判断が厳しいねー。そもそも質問者さんがDequeというものを理解しているかですよね。Stackが使用不推奨になっていなければ今回の場合はStackで実装でいいと思いますけどね。

[anndonut]

ちょい直しで済んだので、もう一つの回答の方でStack<Integer>をDeque<Integer>に直しておきました。swordoneさん、ご指摘ありがとうございます。

[gyro16]

if(num > 0)で並列でpushしていてなぜ0以下がpushされないのですか？
num-2,num-1ではチェックしていませんよね？

[swordone]

そもそも質問者はIntStackというおそらくオリジナルのクラスを使っているのにあなたが勝手にStackを使いだしたんだから、
「質問者がDequeを理解しているか」というのはお門違い。

[gyro16]

numが減っていく機序はどうなってるのですか？
デバッグでブレークポイントで見たのですがよく分かりません。

[anndonut]

swordoneさん、おっしゃる通りです。というかIntStackというクラスを使っているからこそ他の回答者さんはなかなか手を出すことができずに、私とgyro16さんのほうで忖度して回答しているということなんだと思います。

[anndonut]

gyro16さん、このコードは分かりづらいので、もう一つのコードの方で解説させて頂きます。