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問とその解法~

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

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