新・明解Javaで学ぶアルゴリズムとデータ構造

戻る  

演習5-5の解答

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

// 演習5-5
// メソッドrecur3の非再帰的実現

import java.util.Scanner;

class Recur3 {

   //--- メソッドrecurの非再帰的実現 ---//
   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;

            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);
   }
}

戻る