エンジニア実践的基礎: 再帰 夢の中の夢

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

再帰とは

再帰は脱初心者の鬼門です。再帰で苦労する人は多いです。しかし再帰なしでは、基礎的なデータ構造とアルゴリズムを理解できず、さまざまな発展的なことも表面的な理解で終わってしまいます。

一般的な再帰の説明はフィボナッチ数列や階乗などの数学的概念を用いたものです。しかし、下手に数学を出すとそれ自体が理解の妨げになります。それに再帰は他のデータ構造とアルゴリズムを通して徐々に身に付くものです。つまり習うより慣れろです。

ですから、ここでは数学を使わずにイメージだけでなんとなく理解できるように説明します。

皆さんは夢の中で夢を見たことがありますか？現実の世界で寝た後に、夢の世界でも寝ることができれば、夢の中で夢を見ることになります。

インセプションという有名な映画がありますが、まさに夢の中の夢の中の夢の中の…と何層にも渡って夢を見る世界が描かれています。

これはまさに再帰そのものです。

夢の中で夢を見る

まず夢を見る前の自分をイメージしてください。その自分が寝て夢を見ます。すると、夢の中の自分になります。その自分が寝て夢を見ます。そして、その夢の中の自分になります。その自分が寝て夢を見ます。これを繰り返します。

これを繰り返すと無限に夢の中に入っていきます。再帰では通常、無限ループを避けるためにベースケースと呼ばれる、再帰を止める条件が入ります。

この例では3回まで夢を見ることができます。

もっと正確に言えば、再帰は自分自身を呼び出すことです。「夢の中に入る」という呼び出しを、夢の中に入った後に「再び実行」します。

同じ構造を保ちながら深く深く沈んでいくイメージが再帰になります。

もう一つ重要なポイントは、ベースケースに到達したら、最初の呼び出しまで逆戻りすることです。第３層の夢に到達したら、夢から覚めて第二層の夢に戻ります。再び夢から覚めて、第一層の夢に戻ります。そして再び夢から覚めて現実の世界に戻ります。

夢から覚めて戻っていく

実装

このイメージを実装すると次のようになります。

def 夢を見る(レベル, 最大レベル):
    # ベースケース: 最も深い層に到達した場合
    if レベル > 最大レベル:
        print("最も深い夢の層に到達しました！")
        return

    # 現在の層にいることを表示
    print(f"夢のレベル {レベル} に入ります。")

    # 次の夢の層に入る
    夢を見る(レベル + 1, 最大レベル)

    # 次の夢の層から戻ってきたことを表示
    print(f"夢のレベル {レベル} から戻ります。")

# 実行例: 3層の夢をシミュレート
最大レベル = 3
夢を見る(1, 最大レベル)

まとめ

初めて再帰を習う人は今回の解説を聞いても理解できないと思います。仮に理解できても、他のデータ構造とアルゴリズムで再帰で確実に混乱します。

心配しないでください。それは普通です。再帰は何度も何度も繰り返し間違えることで身に付く概念です。

「習うより慣れろ」なので、こんなイメージなんだなぁという感じで考えていただければ OK です。