ITOO's Blog

プログラミングを語る

再帰関数を理解して使いこなす!その1

はじめに

再帰関数を使わなきゃいけない場面はそう多くないように思います。それでも時たま再帰処理で書いたほうが明らかに短く簡潔コードをかける(例えば木構造を扱うみたいな)ときがやってきます。そのたびに苦手意識を持っていた再帰関数ですが、最近少しずつその感覚がなくなってきました。そのため、同じように苦手意識を持っているエンジニアにむけて数回に分けて記事を書きたいと思います。 ※ 私なりの解釈が多分に含まれていますので正確ではないかもしれません、理解の助けになればと思います。

再帰関数とは

ある関数の中で自分を呼ぶような関数のことです。再帰的な構造を持ったアルゴリズムを実装するときによく使われます。関数型言語(Haskel, Scala, Lispなど)では頻繁に使われる手法で、これは純粋な関数型言語ではデータを不変なものとして扱うという特性からきています。一度生成された変数は初期化時の値から変更されないことが保証されているということです。ここで疑問を持った方はいませんでしょうか?よく見る手続き型(Java, PHPなど)のfor文は関数型でどうやって書くのか。。

<?php

// 普通に書くとこう
for ($i = 0; $i < 10; $i++) {
    echo $i;
}

// 再帰関数では下のようにかけます
function echoFunc($i = 0) {
    if ($i < 10) {
        echo $i;
        echoFunc($i + 1);
    }
}
echoFunc();

基本的にはfor文で書ける処理は再帰関数で表現することができます。ただし末尾再帰を行わない再帰関数ではスタックを消費するためfor文に比べ非効率です。そして関数呼び出しは普通ですとオーバーヘッドがあるため簡単なループ処理ではfor文のほうが適していると言っていいでしょう。

では、なぜ再帰関数を理解するのか、それははじめにも述べた通り再帰関数は再帰的なアルゴリズムにとても適しており簡潔に記述できるからです。また、木構造という重要なデータ構造を扱うときに再帰処理がよく使われます。

再帰処理を考えるときのポイント

  1. まず終了条件を考える
  2. 再帰を考えるときは木構造を思い浮かべる
  3. 「関数呼び出し」は「ノード生成」である
  4. return文は木を登る処理である
  5. for文の中にある関数呼び出しはあるノードから子ノードを展開する処理である。
  6. 具体的にn - 1回目の値を考え、そこからn回目の値にするにはどうするかを考える

※ 番号が付いていますが順番は関係ありません

乗算を再帰処理で考える

*演算子を使わないで、正の整数を掛け合わせる再帰関数を書いてみます。考え方としては15 x 4は15を4回足すことで求めることができます。引数でa, bを受け取ったときにbはaを足し算する回数をカウントする変数と考えて1ずつ引いていきます。よって終了条件はbが0になったときです。まだ説明が足りませんがコードは短いので早速書いてみます。言語はRubyです。

# パターン1
def product1(a, b)
  if b.zero?
    return 0
  end

  a + product1(a, b - 1)
end

# パターン2
def product2(a, b, result = 0)
  if b.zero?
    return result
  end

  product2(a, b - 1, result + a)
end

木構造を想像する

パターン1とパターン2の違いはなんでしょうか?ちなみにRubyは最後に評価された値が関数の戻り値になります。 よく見てみると引数と戻り値が違うことがわかると思います。再帰処理を考えるときのポイントの3, 4を思い出し木構造を書いてみます。ノードの値はそのときの計算結果を示しています。

パターン1

f:id:arinko7478:20181011223148p:plain


パターン2

f:id:arinko7478:20181011223224p:plain

再帰関数のパターン

処理を行うタイミングは大きく2つに分けられると思っています。パターン1とパターン2の違いはそこにあります。

  1. 木を登るとき:関数を抜ける = returnする、もしくは関数ブロックを抜ける
  2. 木を降りるとき:自分を呼び出すとき、もしくはその前

パターン1では木を登るときに処理を行います。そのため木を降りている間は計算する情報をスタックしていく必要があります(内部で行われている)。登るときにスタックから情報を取り出し計算式を組み立てていくような感じで、計算自体は最後の最後まで実行されないのでノードの値は0のままです。

パターン2では木を降りるときにその都度計算が行われ、終了条件に達したときには結果が求まっている状態です。なので登るときにはただ結果を返していくのみとなります。そして実は末尾再帰と呼ばれているものになります。

まとめ

再帰処理は一行ずつ処理を追っていると混乱してしまうようなものでも、パターンを覚えてしまえば再帰関数を読んだり再帰を使って問題を解くこともすばやくできるようになるはずです。今回はとてもシンプルな例で説明をさせてもらいました。そのため、再帰処理を考えるときのポイントの5, 6を今回は使っていません。次回はもう少し複雑な例を取り上げてすべてのポイントをカバーしていこうと思います。また、今後もRubyを使っていくので余裕があれば速度計測を行ったり、再帰処理を組み立てるだけではなく言語特性を踏まえてどういったアプローチが適切なのかを考えて行く予定です。

最後に

最後に、再帰関数で使われるパターンを紹介しましたがまだ私自身、勉強中でもありますのでここが間違っているとか、こういったパターンも説明してほしかったなどご意見・感想を切望してます ではでは(^▽^)

参考資料

末尾再帰による最適化

今年こそは再帰関数を理解しよう! - くろのて

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

Abstract Factoryパターンについて考える

はじめに

GoFデザインパターンでAbstract Factoryパターンについて考える機会があったのでここに残そうと思います。デザインパターンを学習していてコードは理解できるのですが、実際に問題に「どう適用するか」ってところで詰まってしまうことが多いなあと思うこの頃。ゆくゆくは具体的に役立ちそうな実装を紹介したいのですが、今回は「鍋」にたとえてAbstract Factoryとその利点について重点的に書いていきます。

概要

Abstract Factoryを直訳すると「抽象的な工場」という意味、簡単に行ってしまうとオブジェクトを作る工場を作るパターンのこと。ここで「工場」というのはもちろんクラスのことです。

参考にしたページによると

AbstractFactory パターンとは、 インスタンスの生成を専門に行うクラスを用意することで、整合性を必要とされる一連のオブジェクト群を間違いなく生成するためのパターンです。

8. AbstractFactory パターン | TECHSCORE(テックスコア)

鍋に例える

正直まだわからないと思います(僕はわかりませんでした)。そこで鍋にたと例えてみたいと思います。

鍋がオブジェクトで、

f:id:arinko7478:20180917141829j:plain

具材がそのメンバ変数とします。

f:id:arinko7478:20180917141912j:plainf:id:arinko7478:20180917141916j:plain

鍋を作るのに必要なもの

  • スープ(鶏ガラスープ、キムチスープ、トマトスープ...etc)
  • メインの具材(鶏肉、牛肉、豚肉 ...etc)
  • 野菜たち(にんじん、じゃがいも、玉ねぎ ...etc)
  • そのたの具材(ご飯、麺 ...etc)

ざっと普通の鍋でしたらこんなところでしょう。

鍋クラスを作る

<?php

class HotPot 
{
    /** 鍋  */
    private $pot;

    /** スープ */
    private $soup;

    /** メインの具材 */
    private $main_guzai;

    /** 野菜 */
    private $vegetables;

    /** その他の具材 */
    private $othre_guzai;

    public function __construct($soup) 
    {
        $this->soup = $soup;
    }

    /** 以下は具材を加える関数群 */
    
    public function addSoup($soup)
    {
        $this->soup = $soup;
    }

    public function addMainGuzai($main_guzai)
    {
        $this->main_guzai = $main_guzai;
    }

    public function addVegetables($vegetables)
    {
        $this->vegetables = $vegetables;
    }

    public function addOtherGuzai($othre_guzai)
    {
        $this->othre_guzai = $othre_guzai;
    }
}

ここで「工場」は「料理人」?

料理人は鍋に合わせて具材を正しい順番で(火の通りなどを考えて)入れる必要が有る。

下記はミルフィーユ鍋をつくる 「料理人クラス」

<?php
class Cook
{
    public function prepareMillefeuille() 
    {
        // 鍋の用意
        $hot_pot = new HotPot();

        // かつおのだし汁を入れる
        $hot_pot->addSoup(new KatuoSoup());

        // 豚肉を入れる
        $hot_pot->addMainGuzai(new Butaniku());

        // 野菜たちを入れる
        $hot_pot->addVegetables([
            new Hakusai(),
            new Tamanegi()
        ]);

        // 締めのご飯を入れる
        $hot_pot->addOtherGuzai([
            new Rice()
        ]);
    }
}

「料理人」は「プログラマ」?

間違わないようにすべてのメンバ変数に値を入れてオブジェクトを作るのは難しいので、料理人がどうすれば楽になるかを考えれば自ずとプログラマが楽になっていくはず

ここで、ついにミルフィーユ鍋生成クラス(工場)を作ります。

<?php
require_once __DIR__ . '/Factory.php';

/**
 * ミルフィーユ鍋に必要な具材を持っているクラス
 */
class MillefeuilleFactory extends Factory
{
    public function getSoup()
    {
        return new KatuoSoup();
    }

    public function getMainGuzai()
    {
        return new Butaniku();
    }

    public function getVegetables()
    {
        return [
            new Hakusai(),
            new Tamanegi()
        ];
    }
    public function getOtherGuzai()
    {
        return [
            new Rice
        ];
    }
}

Factory抽象クラスについてはあとで説明します。このクラスができることで料理人はgetメソッドを呼んでオブジェクトに値を入れるだけになりました。さらに各具材の「したごしらえ」などの処理もこのクラスに書いておくことができます。

<?php
require_once __DIR__ . 'HotPot.php';
require_once __DIR__ . 'factories/MillefeuilleFactory.php';

class Cook
{
    public function prepareMillefeuille() 
    {
        // 鍋の用意
        $hot_pot = new HotPot();
        $millefeuile_factory = new MillefeuilleFactory();

        // かつおのだし汁を入れる
        $hot_pot->addSoup($millefeuile_factory->getSoup());

        // 豚肉を入れる
        $hot_pot->addMainGuzai($millefeuile_factory->getMainGuzai());

        // 野菜たちを入れる
        $hot_pot->addVegetables($millefeuile_factory->getVegetables());

        // 締めのご飯を入れる
        $hot_pot->addOtherGuzai($millefeuile_factory->getOtherGuzai());
    }
}

もっと料理人(プログラマ)を楽にする

一度でてきたFactory抽象クラスを理解してもっと楽にいろいろな鍋が作れるようにしていきたいと思います。 まずFactory抽象クラスは下のようになっています。

<?php
abstract class Factory
{
    public abstract function getSoup();
    public abstract function getMainGuzai();
    public abstract function getVegetables();
    public abstract function getOtherGuzai(); 
}

もう一度Cookクラスを見てもらいたいと思いますが、Factory抽象クラスを継承したクラスを使って鍋の準備を行うという縛りがあれば料理人のやることはどの鍋でも同じだということです。ただ違うのは何鍋の生成用インスタンスをつくるかだけです。

<?php
class Cook
{
    public function prepare($nabe)
    {
        // 鍋の用意
        $hot_pot = new HotPot();

        // 鍋のファクトリーを作成
        $factory = $this->createFactory($nabe);

        // スープを入れる
        $hot_pot->addSoup($factory->getSoup());

        // メインの具材を入れる
        $hot_pot->addMainGuzai($factory->getMainGuzai());

        // 野菜たちを入れる
        $hot_pot->addVegetables($factory->getVegetables());

        // その他の具材を入れる
        $hot_pot->addOtherGuzai($factory->getOtherGuzai());
    }

    public function createFactory($nabe)
    {
        if ($nabe === 'ミルフィーユ鍋') {
            return new MillefeuilleFactory;

        } elseif ($nabe === 'キムチ鍋') {
            return new KimutiFactory;

        } elseif ($nabe === 'すき焼き') {
            return new SukiyakiFactory;
        }
    }
}

鍋の名前によって生成するインスタンスを振り分けています。これで鍋生成クラスを増やして、それをCookに教えてやる(createFactoryメソッドを少し修正)するだけでレパートリーが増やすことができるようになりました。

まとめ

鍋に例えることでAbstract Factoryの便利さがわかったのではないでしょうか?だいぶ遠回りな説明になってしまった気もしますが、このパターンを適用することで複雑な生成過程が必要なクラスを簡単に生成することができるようになります。まず抽象クラスを用意して、それを継承したオブジェクト生成クラスを作ってやることで難しい生成処理を共通化してしまうのです。

最後に

OOPデザインパターンで有用な使い方について試行錯誤しています。なにかご指摘、要望等いただけたらうれしいです。これからもプログラミングに役立つ記事を書いていきたいと思います!ではでは( ̄ω ̄)

参考資料

Head Firstデザインパターン ―頭とからだで覚えるデザインパターンの基本

Head Firstデザインパターン ―頭とからだで覚えるデザインパターンの基本

増補改訂版Java言語で学ぶデザインパターン入門

増補改訂版Java言語で学ぶデザインパターン入門

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

素のPHPでディスパッチャを作ってみた

はじめに

手軽に使えるディスパッチャーを作りました。最小限の機能で使いがっていいので、フレームワークを使うほどでもないってときにつかえるかもしれません!ちなみに前回テンプレートエンジンをつくりました。

syarig.hatenablog.com

ディスパッチャーとはなにかについてはこのサイトが分かりやすく説明してくれてます。

ディレクトリ構成

app
├── classes
│   └── controller
│       └── HelloController.php
├── configs
│   └── routes.php
├── public
│   └── index.php
└── utils
    └── Dispatcher.php

まずは、htaccessなどでindex.phpにリダイレクトするように設定しておいてください。そして、今回作ったディスパッチャーでリクエストをさばくようにするとMVCモデルの感じがでてくると思います。アプリで使う定数(ルートパス)などもindex.phpに書いていくといいのではないでしょうか。

今回はディスパッチャーのテストとしてHelloControllerindexActionを用意しました。ルーティング設定はconfigs/routes.phpに書いてあります。もし使われる場合はここにルーティングを追加するといいでしょう。

ディスパッチャー(app/public/index.php

<?php

/**
 * Class Dispatcher
 * uriに従ってコントロータとアクションを振り分ける
 */
class Dispatcher
{
    const CONTROLLER_DIR = 'classes/controller' . DIRECTORY_SEPARATOR;

    // コントローラファイルへのパス
    private $controller_path;

    // 設定ファイルを正規表現の形にしたものが入る
    private $patterns;

    // コントローラ名
    private $controller;

    // アクション名 ex.) indexAction
    private $action;

    // アクションに渡される引数 ex.) $args['name']
    private $args;

    // リクエストがあったURI
    private $request_uri;

    /**
     * コンストラクタでルーティングの初期設定を行う
     *
     * @param string[] $routes
     */
    public function __construct($routes)
    {
        $this->controller_path = ROOT . self::CONTROLLER_DIR;
        $this->patterns = $this->setPatterns($routes);
        if ($this->resolve() === false) {
            $this->controller = $routes[DIRECTORY_SEPARATOR]['controller'];
            $this->action = $routes[DIRECTORY_SEPARATOR]['action'];
        }
    }

    /**
     * 正規表現に変換する。ex.) {action} -> (?P<action>[^/]+)
     * 
     * @param string $route
     * @return string 正規表現の文字列
     * 
     */
    private function tokenToRegexp($route)
    {
        if (preg_match('/{(.+?)}/', $route, $matches)) {
            $route = "(?P<{$matches[1]}>[^/]+)";
        }
        return $route;
    }

    /**
     * ルーティングURLを正規表現に変換する
     * ex.) /{name} -> /(?P<name>[^/]+)
     * 
     * @param string[] $route
     * @return string[] ルーティングの対応を示す配列
     */
    private function setPatterns($routes)
    {
        $patterns = [];

        foreach ($routes as $url => $route) {
            $url = rtrim($url, DIRECTORY_SEPARATOR);
            $url = ltrim($url, DIRECTORY_SEPARATOR);
            $tokens = explode(DIRECTORY_SEPARATOR, $url);
            $tokens = array_map([$this, 'tokenToRegexp'], $tokens);

            $pattern = DIRECTORY_SEPARATOR . implode(DIRECTORY_SEPARATOR, $tokens);
            $patterns[$pattern] = $route;
        }
        return $patterns;
    }

    /**
     * URLとルーティングパターンからコントローラ、アクション、引数を決める
     * 
     * @return bool
     */
    public function resolve()
    {
        // リクエストURIの末尾の'/'を削除する。
        $this->request_uri = rtrim($_SERVER['REQUEST_URI'], DIRECTORY_SEPARATOR);

        if (DIRECTORY_SEPARATOR !== substr($this->request_uri, 0, 1)) {
            $this->request_uri = DIRECTORY_SEPARATOR . $this->request_uri;
        }

        foreach ($this->patterns as $pattern => $route) {
            if (preg_match('#^' . $pattern . '$#', $this->request_uri, $matches)) {
                $route = array_merge($route, $matches);
                $this->controller = $route['controller'];
                $this->action = $route['action'];

                unset($route['controller']);
                unset($route['action']);

                $this->args = $route;
                return true;
            }
        }
        return false;
    }

    public function getRequestUri()
    {
        return $this->request_uri;
    }

    /**
     * アクションを実行する
     */
    public function dispatch()
    {
        $controller_file = $this->controller_path . $this->controller . '.php';

        if (file_exists($controller_file) === false) {
            throw new InvalidArgumentException("{$controller_file}が存在しません。");
        }

        require_once $controller_file;

        $controller_instance = new $this->controller();
        $action_method = $this->action . 'Action';

        if (method_exists($controller_instance, $action_method) === false) {
            throw new InvalidArgumentException("{$action_method}が存在しません。");
        }

        $controller_instance->$action_method($this->args);
    }
}

少しコードが複雑だと思うのでコメントを多めに書きました。簡単に説明をするとリクエスURIからコントローラのインスタンスを作成して、そのコントローラーのアクションメソッドを呼びだしています。アクションメソッドをget_xxxみたいな指定にしたりしてGETメソッドだけを受けとるみたいなことをすればよりフレームワークっぽくなる気がします。

ルーティングの設定(app/configs/routes.php

<?php

return [
    '/' => [
        'controller' => 'HelloController',
        'action' => 'index'
    ],
    '/{name}' => [
        'controller' => 'HelloController',
        'action' => 'index'
    ],
];

ルーティングの設定ファイル。{変数名}という形で動的ルーティングができるようになっています。

app/public/index.php

<?php

require_once __DIR__ . '/../utils/Dispatcher.php';

// アプリのルート
const ROOT = __DIR__ . '/..' . DIRECTORY_SEPARATOR;

$dispatcher = new Dispatcher(include_once __DIR__ . '/../configs/routes.php');

try {
    $dispatcher->dispatch();

} catch (InvalidArgumentException $e) {
    echo "404, Page Not Found\n";
    echo $e;

} catch (Exception $e) {
    echo "500, Internal Server Error\n";
    echo $e;
}

このファイルにアクセスが集まることになります。また、「コントローラやアクションが存在しないとき」 = 「ページが存在しないとき」は404 Page Not Foundを表示します。ほんとうは独自に例外を定義して、404ページも用意するといいと思います。

実行する

app/public/配下でphp -S localhost:8080とコマンドを打ってから、ブラウザでlocalhost:8080/にアクセスしてみてください。Hello Worldと画面に表示されたら成功です!また、試しにlocalhost:8080/HogehogeとしてみるとHello Hogehogeと表示されるはずです!

まとめ

ディスパッチャーは百数十行程度ですが、シンプルで使い易いものができたと思います。前回作ったテンプレートエンジンと組み合わせるとフレームワークっぽくなってきたのがわかると思います!ですが、まだまだフレームワークと呼ぶには足りないものがあります!セッションやリクエスト、レスポンスなども専用のクラスを用意したほうがよいでしょう。次回はSessionクラスを作ってみたいと思います。

最後に

今回はテンプレートエンジンと組み合わせる予定でしたが、結構な分量になってしまったのでここで終わりたいと思います。このブログではこんな感じでフレームワークのパーツを一つずつ作っていきオレオレフレームワークを作っていきます。PHPの学習などにもお役に立てたら幸いです。 また、「こんな風にしたらもっとよくなるよ」「ここ間違ってるよ」などなど意見、質問、アドバイスをいただけたら嬉しいです。

参考資料

PHPフレームワーク Laravel入門

PHPフレームワーク Laravel入門

改訂 FuelPHP入門

改訂 FuelPHP入門

素のPHPでテンプレートエンジンを作った

はじめに

手軽に使えるテンプレートエンジンを作りました。ディレクトリ構成はこんな感じ

app
├── sample.php
├── templates
│   └── index.php
└── utils
    └── Template.php

テンプレートエンジン

<?php

class Template
{
    const DEFAULT_TPL_PATH = __DIR__ . '/../templates';

    public $tpl_path;

    public function __construct()
    {
        $this->tpl_path = self::DEFAULT_TPL_PATH;
    }

    /**
     * @param string $path
     */
    public function setTemplatePath($path)
    {
        $this->tpl_path = rtrim($path, '/');
    }

    private function escapeArrayRec(&$attr_dict)
    {
        foreach ($attr_dict as $key => $val) {
            if (is_array($val)) {
                $attr_dict[$key] = $this->escapeArrayRec($val);
            } else {
                $attr_dict[$key] = htmlspecialchars($val, ENT_QUOTES, 'UTF-8');
            }
        }
        return $attr_dict;
    }

    /**
     * @param string $tpl_file
     * @param array $attr_dict
     */
    public function render($tpl_file, $attr_dict = [], $escape = true)
    {
        if ($escape) {
            $this->escapeArrayRec($attr_dict);
        }

        extract($attr_dict);

        include($this->tpl_path . $tpl_file);
    }
}

最低限の機能しかありませんが、簡単なアプリでビューと処理を分けたいときは重宝するのではないでしょうか。 エスケープを行ってるので、Javascriptが埋め込まれても実行されません。

index.php

テンプレートファイル

<html>
<head>
    <meta charset="utf-8">
</head>
<body>
<h1><?= $name ?>さん</h1>
<h2>趣味</h2>
<ul>
    <?php foreach ($favorites as $favorite): ?>
        <li><?= $favorite ?></li>
    <?php endforeach; ?>
</ul>
</body>
</html>

sample.php

実際に表示を行うファイル

<?php

require_once __DIR__ . "/utils/Template.php";


$tpl = new Template();
$name = 'hogehoge';
$favorites = ['音楽', 'サッカー', '', '家電'];
$tpl->render('/index.php', compact('name', 'favorites'));

app/配下でphp -S localhost:80とコマンドを打ってから、ブラウザでlocalhost:80/sample.phpと実行してみてください。 値が埋め込まれてindex.phpが表示されたら成功です。

まとめ

PHPの機能を使っただけの簡単なテンプレートエンジンですが、ショートタグなども駆使すれば使えば結構使い勝手は良いのではないでしょうか。 さすがHypertext Preprocessorです。PHPの学習などにもお役に立てたら幸いです。

最後に

次は、このテンプレートエンジンを生かしてもう少しMVCモデルっぽくしてみたいと思います。お楽しみに。 「こんな風にしたらもっとよくなるよ」「ここ間違ってるよ」などなど意見、質問、アドバイスをいただけたら嬉しいです。

参考資料