再帰（Recursion）を解説してみる

Tech

cover

はじめに

「再帰」について言語化する練習記事。再帰という言葉や使われ方を説明するのは至難の業である。どう分かりやすく説明できるだろう？と思ったので、記事にまとめて自分なりの解答を作っておこうと思う。この記事を通して再帰をイメージできることを目標とする。

再帰とはなにか？

Wikipediaから引用すると、以下のような説明が記載されている。

再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。自己相似の記事も参照のこと。

…難しい。確かに「再帰」の意味を表現できている説明だと思うが、それでも抽象的な説明であることには変わりない。

プログラミングにおける再帰

となると、やはり具体例から見たほうが理解しやすいと思う。早速実際のコードから見てみよう。例としては階乗の計算（5の階乗 = 5! = 5 * 4 * 3 * 2 * 1 = 120）がピッタリだろう。

まずは一番シンプルに再帰を利用したコードが以下である。

int factorial(int a){
    if(a == 0) return 1;
    return a * factorial(a-1);
}

int main(){
    fact(5);  // 120
}

factorial関数のなかで同様の関数を呼び出すことで、階乗計算を実行していく再帰を活用したコードである。 再帰関数には「終了条件」がある。今回の場合は a == 0が該当し、aが0になるまで、aを一つずつ減算し階乗の計算が実行される。 ある種の自己矛盾のように見えるだろうが、プログラムの世界ではこのコードは何事もなく動作する。

上記の動きをよくイメージすると、再帰は「繰り返し構文」に書き換えることができる。

int main(){
    int result = 1;
    for(int i = 5; i > 0; i--){
        result *= i;
    }
    return result;
}

この繰り返し構文であれば、意味を理解できる人も多いと思う。再帰では「繰り返し構文とセマンティクスは同一」とみなせて、このテクニックを活用することでコード量や見通しを良くなる場合がある。

また再帰には幾つかパターンがあり、「末尾再帰」と呼ばれる方式に変換すると階乗のコードは以下のようになる。

int factorial(int x){
    int inner_factrial(int a, int b){
        if(a == 0) return b;
        return inner_factorial(a - 1, a * b);
    }    
    return inner_factorial(x, 1);
}


int main(){
    factorial(5); // 120
}

少し難しくなっているように感じるが、ポイントは最後の if(a == 0) return b;の箇所である。再帰には終了条件があると先述したが、終了条件のときに引数のbを返却している。この値bはこれまでの計算結果の累積値になっており、終了条件のタイミングで累積値（計算結果）を返却している。当然この形式も繰り返し構文に変換できるが、先程紹介した例とほとんど同じコードになるので割愛する。

次に視点をかえて、データ構造の視点から「再帰」を紹介してみよう。

データ構造としての再帰構造

以下に二分木におけるノードを表現するコードを示す。

class Node {
    int val;
    Node left;
    Node right;
}

このコードの場合、二分木がどのような構造かはここでは気にする必要はない。重要なのはクラスのフィールドとして、自身のクラスを使っていることである。この関係性はまさに自己言及的であり、再帰構造を持ったクラス定義ということができる。

その他の回帰

他にも再帰をいくつか紹介しよう。

DNSの名前解決の方法の一つに「再帰的問い合わせ」がある。ドメイン名の名前解決する問い合わせを指す。名前解決の仕組みを思い出してもらいたいが、まずトップレベルドメインからドメイン名を解決し、その下のDNSサーバに問い合わせて、と名前が解決できるまで問い合わせを繰り返し行う、という意味合いで「再帰」となっていることがわかる。

少々変わり種を紹介すると、Unixにおけるフリーソフトウェア群を開発する「GNUプロジェクト」というプロジェクトがある。 このGNUは GNU's Not Unix!という再帰的な略語である（この場合、終了条件が見当たらないが…）。

さいごに

ここまでの説明で再帰のイメージができるようになっただろうか。再帰を使いこなせるようになるとプログラミングが一段と面白く感じれるはずなので、ぜひ習得してもらいたい。

どうでもよいが、コンピュータサイエンスにおいて「変数は箱だ」のようにアナロジーを活用することは多いが、再帰におけるアナロジーって何かあるだろうか？などと思ったりした。

Home