επιστημη様のエントリより有名な、あまりに有名な

再帰処理で書くところを再帰を使わないで書き換えるとどうなるかという話題です。

木構造を考えたとき、その枝を走査する際に再帰で処理を書くと書きやすいのですが、 他にもいくつかアプローチの仕方があるので紹介しましょう。

サンプルコード

まずは木構造のノードの抽象クラスからです。

import java.util.LinkedList;
import java.util.List;

/** ノードの抽象クラス */
public abstract class Node {
  /** 名前 */
  private String name;

  /** コンストラクタ */
  public Node(String name) {
    this.name = name;
  }
  /** 名前の取得 */
  public String getName() {
    return this.name;
  }

  /** toString()をオーバーライドして名前が出力されるようにしておく */
  @Override
  public String toString() {
    return this.getName();
  }

  /** Compositeパターンによるノードの出力処理 */
  public abstract void printNode();

  /** Visitorの受け入れ処理 */
  public abstract void accpent(Visitor visitor);

  /** Visitorのインターフェース */
  public static interface Visitor {
    /** 単数形ノード */
    void visit(SimpleNode node);
    /** 複数形ノード */
    void visit(MultipleNode node);
  }
  /** ノード名を出力するVistorの実装 */
  public static class PrintVisitor implements Visitor {
    /** 単数形ノード */
    @Override
    public void visit(SimpleNode node) {
      System.out.println(node);
    }
    /** 複数形ノード */
    @Override
    public void visit(MultipleNode node) {
      System.out.println(node);
      for (Node subNode : node.getChildlen()) {
        subNode.accpent(this);
      }
    }
  }

  /** 再帰処理によるノードの出力処理 */
  public static void 再帰(Node node) {
    System.out.println(node.getName());

    if (node instanceof MultipleNode) {
      MultipleNode multipleNode = (MultipleNode) node;
      for (Node subNode : multipleNode.getChildlen()) {
        再帰(subNode);
      }
    }
  }

  /**
   * 再帰を使わず、Listのループで処理する方式
   */
  public static void list方式(Node rootNode) {
    List<Node> nodeList = new LinkedList<Node>();
    nodeList.add(rootNode);

    for (int i=0; i<nodeList.size(); i++) {
      Node node = nodeList.get(i);
      System.out.println(node.getName());

      // 複数形の場合は子ノードを処理対象Listの次のインデックスに加える
      if (node instanceof MultipleNode) {
        MultipleNode multipleNode = (MultipleNode) node;
        for (Node subNode : multipleNode.getChildlen()) {
          int index = i + 1;
          if (index < nodeList.size()) {
            nodeList.add(index, subNode);
          } else {
            nodeList.add(subNode);
          }
        }
      }
    }
  }
}

次は木の末端、配下に子を持たないノード。

/** 単数形のノード */
public class SimpleNode extends Node {

  /** コンストラクタ */
  public SimpleNode(String name) {
    super(name);
  }

  /** Compositeパターンによるノードの出力処理 */
  @Override
  public void printNode() {
    System.out.println(this);
  }

  /** Visitorの受け入れ */
  public void accpent(Visitor visitor) {
    visitor.visit(this);
  }
}

最後に配下に子を持つ枝のノード。

/** 複数形のノード */
public class MultipleNode extends Node {
  /** 子ノード */
  private List<Node> childlen;

  /** コンストラクタ */
  public MultipleNode(String name) {
    super(name);
    this.childlen = new ArrayList<Node>();
  }

  /** 子ノードの追加 */
  public void addChild(Node node) {
    this.childlen.add(node);
  }

  /** 子ノードのListを返す */
  public List<Node> getChildlen() {
    return this.childlen;
  }

  /** Compositeパターンによるノードの出力処理 */
  @Override
  public void printNode() {
    System.out.println(this);
    for (Node subNode : this.getChildlen()) {
      subNode.printNode();
    }
  }

  /** Visitorの受け入れ */
  public void accpent(Visitor visitor) {
    visitor.visit(this);
  }
}

ソース解説

複合的に書いたのでごちゃ混ぜになっていますが、ざっくりと解説です。

本サンプルはノードを走査して名称を表示するだけのシンプルなものです。 基本的にはGoFデザインパターンのCompositeパターンを利用しています。 抽象クラスNodeに対し、子を持たないSimpleNodeと子を持つMultipleNodeの２種類の実装が存在します。

再帰処理

再帰処理はこういった継承関係を持つデータ構造だと扱いにくく、その無理がinstanceof演算子に現れています。

  /** 再帰処理によるノードの出力処理 */
  public static void 再帰(Node node) {
    System.out.println(node.getName());

    if (node instanceof MultipleNode) {
      MultipleNode multipleNode = (MultipleNode) node;
      for (Node subNode : multipleNode.getChildlen()) {
        再帰(subNode);
      }
    }
  }

上位のクラスで複数の子を持つことが確定しているのであればこのinstanceofが不要です。 単複同型で扱おうというCompositeとは相性が悪いという点はありますが、 型の違いによるポリモフィズムを多用しないのであれば、再帰でも問題なく処理が書けます。

Listのループによる書き換え

再帰を敢えて使わないのであれば、list方式()メソッドのような手法も使うことができます。 これは、Listを作業用のワークエリアとして使っており、Listに処理の対象を追加しつつ、 forループで順に処理していくというトリッキーなコードになっています。

深さ優先にするためにListへのadd部分がややこしくなっていますが、 幅優先探査であればListの末尾にaddしていくことで比較的シンプルな記述になります。

ループをまわしているListにどんどん追加していくため、for - each構文だとうまく処理できません。 一応こういった書き方も出来るよ、という程度にとどめておいた方がよいのではないでしょうか。

Compositeパターンによる書き換え

Compositeパターンでは木構造が非常に単純に処理できます。 printNode()メソッドが該当処理なのですが、抽象クラスNodeで宣言されており、 SimpleNodeとMultipleNodeで別々の実装が書かれています。

  /** Compositeパターンによるノードの出力処理 */
  @Override
  public void printNode() {
    System.out.println(this);
  }

とSimpleNodeの実装は自身の名称を出力するだけですが、

  /** Compositeパターンによるノードの出力処理 */
  @Override
  public void printNode() {
    System.out.println(this);
    for (Node subNode : this.getChildlen()) {
      subNode.printNode();
    }
  }

MultipleNodeでは自身の出力と、各子ノードの出力のループが記述されています。 子ノードはその実態がSimpleNodeか、MultipleNodeかでポリモーフィズムにより分岐するしかけです。

Compositeパターンの場合、Nodeの実装の種類が増えた際に追加の実装クラスを定義するだけで拡張が行えます。

Visitorパターンによる書き換え

VisitorパターンはGoFデザインパターンの中でもっとも難解なのではないかと思います。 動きを追いかけるのが難しいのですが、Visitorインターフェースが定義され、PrintVisitorクラスが実体となります。

VisitorクラスではNodeの種類が増えたりした場合には大きな修正コストがかかります。 Visitorインターフェースの変更と、それにともなう各Visitorの実装クラスの修正が必要です。 しかし、Visitorの実装を新たに作るだけで木構造をたどりながら行う処理のバリエーションを容易に増やせます。

今の場合、ノード名を出力するという代物でしたが、Nodeクラスに他にもフィールドがあった場合、 木構造を手繰りながらやる処理というのは多様であると考えら得ます。 Visitorパターンはこの部分を用意に拡張することができるのです。

Compositeパターンの場合はこういった処理ごとにNodeクラスにメソッドを追加し、 Nodeの実装クラスにも手を加える必要があります。

CompositeパターンはNodeの種類を増やすのが簡単、Visitorパターンは木構造を 手繰りながら行う処理を増やすのが簡単、という特徴があります。

このように、同じ処理をいろんな手法で書くことで、それぞれの特色がより鮮明に見えてくるのではないでしょうか。