Pythonで再帰関数を使う方法！階乗・フィボナッチ数列の実装例

1. 再帰関数とは？

1. 再帰関数とは？

Pythonの再帰関数とは、関数の中で自分自身をもう一度呼び出すことで処理を進める仕組みを指します。たとえば、大きな作業を小さく分けて、同じ手順を何度も繰り返しながら解決していくようなイメージです。身近な例で言うと、箱の中にさらに同じ形の小さな箱が入っており、その中を順番に確かめていくような流れに似ています。

再帰関数を理解するうえで特に大事なのは、「終了条件」と「再帰呼び出し」の2つです。終了条件は「ここまで来たら処理を終える」という基準で、これがないと関数が何度も自分を呼び続けて止まらなくなり、プログラムが強制終了してしまうことがあります。

まずは、再帰の動き方を極めてシンプルな例で見てみましょう。これは数を1つずつ減らしながら0になったら止まる、再帰の基本的な動作を示したものです。

def countdown(n):
    if n == 0:              # 終了条件
        print("終了！")
        return
    print(n)
    countdown(n - 1)        # 再帰呼び出し

countdown(5)

5
4
3
2
1
終了！

このコードでは、countdownが自分自身を呼び出すことで数字を1つずつ減らし、最終的に0になったところで停止します。再帰関数の「小さな問題に分割して同じ処理を繰り返す」という考え方が、直感的につかみやすくなるはずです。再帰は仕組みを理解するととても便利なテクニックなので、ここで動き方をしっかり押さえておきましょう。

2. 階乗の計算を再帰関数で実装

2. 階乗の計算を再帰関数で実装

階乗（かいじょう）とは、ある数字から 1 までの整数をすべて掛け合わせた値のことです。例えば 5 の階乗は 5 × 4 × 3 × 2 × 1 = 120 になります。数が大きくなると計算手順も増えるため、再帰関数の「同じ処理を繰り返す」という考え方がとても相性のよい題材です。

再帰関数で階乗を求めるときのポイントは「小さな問題に分けて考える」ことです。たとえば 5!（5の階乗）は、5 × 4! と書き換えられるように、同じ構造が繰り返されています。この仕組みをそのままコードに落とし込むことで、シンプルで読みやすい実装になります。

def factorial(n):
    if n == 0 or n == 1:    # 終了条件：0 または 1 の階乗は必ず 1
        return 1
    return n * factorial(n - 1)  # 自分自身を呼び出して計算

print(factorial(5))

120

このコードでは、factorial(5) が 5 * factorial(4) を呼び出し、さらに factorial(4) が 4 * factorial(3) を呼び出す…というように、階段を降りるように処理が進んでいきます。最終的に factorial(1) で停止（終了条件）し、そこから順に結果が戻ることで最終的な答えが完成します。初心者でも再帰の仕組みを理解しやすい代表的な例なので、まずはここで動きをきちんとつかんでおくと後の応用がグッと楽になります。

3. フィボナッチ数列の再帰関数

3. フィボナッチ数列の再帰関数

フィボナッチ数列は、プログラミングの学習でよく登場する有名な数列です。0 と 1 から始まり、「次の数 = 1つ前の数 + 2つ前の数」というルールで増えていきます。実際の並びは次のようになります。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

例えば、3番目以降の数は次のように計算されています。

• 2番目の数：1（最初に決めておく値）
• 3番目の数：1（= 0 + 1）
• 4番目の数：2（= 1 + 1）
• 5番目の数：3（= 1 + 2）
• 6番目の数：5（= 2 + 3）

このように、「直前の2つを足す」という同じルールがずっと続くので、再帰関数で表現するのにぴったりな題材です。

def fibonacci(n):
    if n == 0:          # 終了条件その1：0番目の値は 0
        return 0
    elif n == 1:        # 終了条件その2：1番目の値は 1
        return 1
    # それ以外は、1つ前と2つ前を足したもの
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(fibonacci(i))

0
1
1
2
3
5
8
13
21
34

ここでのポイントは、fibonacci 関数の中で fibonacci 自身を呼び出しているところです。例えば fibonacci(5) を呼び出すと、内部では次のような流れで計算が進みます。

• fibonacci(5) は fibonacci(4) + fibonacci(3) を計算する
• fibonacci(4) は fibonacci(3) + fibonacci(2) を計算する
• fibonacci(3) は fibonacci(2) + fibonacci(1) を計算する
• fibonacci(1) と fibonacci(0) は、終了条件なのでそのまま 1 と 0 を返す

このように、大きな問題（5番目の値を求める）を「ひとつ前」と「ふたつ前」の小さな問題に分けていき、最後に 0 と 1 にたどり着いたところで結果が少しずつ積み上がっていきます。再帰関数の「分割して考える」という考え方をつかむのに、フィボナッチ数列はとても良い練習素材です。最初は小さな数で試しながら、どのように呼び出されているか紙に書き出して追いかけてみると、より深く理解できるようになります。

4. 再帰関数の注意点と使いどころ

4. 再帰関数の注意点と使いどころ

再帰関数は便利ですが、何でも再帰で書けば良いわけではありません。呼び出し回数が多すぎるとメモリを使いすぎてエラーになることがあります。特にフィボナッチ数列の再帰は効率が悪いため、数が大きくなると処理が遅くなります。

そのため、再帰関数は「分割して考えられる問題」や「階層構造を持つデータ処理」に向いています。例えばフォルダの中のファイルをすべて調べる処理や、ツリー構造のデータ探索などです。

5. ループとの比較

5. ループとの比較

階乗やフィボナッチ数列は、実はfor文やwhile文でも書けます。再帰関数はコードが短く直感的になる場合がありますが、ループの方が効率的な場合も多いです。状況によって使い分けることが大切です。

6. プログラミング未経験者へのポイント

6. プログラミング未経験者へのポイント

プログラミング初心者の方は、まずは終了条件を必ず書くことを覚えてください。終了条件がないとパソコンが止まる可能性があります。また、最初は小さな数字で試してみて、結果が予想通りになるかを確認すると理解しやすくなります。

Pythonの再帰関数は、数学的な計算だけでなく、パズルの解法やデータ処理など幅広い場面で使えます。繰り返し処理を考えるとき、「自分自身を呼び出す」という考え方を覚えておくと便利です。

まとめ

まとめ

Pythonの再帰関数は、繰り返し処理を簡潔に記述できる便利な仕組みであり、特に階乗計算やフィボナッチ数列のような数学的問題で力を発揮します。再帰呼び出しは「同じ処理を繰り返す」という特徴を自然な形で表現でき、コードの見通しも良くなります。この章では、今まで学んだ内容を整理しながら、再帰関数の特徴や使いどころ、注意点について改めて深く理解できるようにまとめています。Pythonで階層構造のデータを扱う場面や、分割統治法のように問題を小さく分けて考えるアルゴリズムなど、再帰の考え方が役立つ場面はとても多く、こうした考え方はプログラミングだけではなく論理的思考力を高める上でも重要です。 また、Pythonで再帰関数を扱う際には必ず終了条件を設定し、無限に繰り返す状況を避けることが大切です。終了条件と再帰処理のバランスを理解することで、より確実で読みやすいプログラムを書くことができます。特にフィボナッチ数列の場合、単純な再帰実装は処理が重くなりやすいため、効率の面にも注意が必要です。処理の流れを頭の中で整理しながら、小さな値で動作確認をすることが理解を深めるポイントです。 そして、再帰関数は数学的な問題に限らず、フォルダ探索やツリー構造の解析など、現実のプログラミングにおいても多くの応用場面があります。再帰を知ることで扱える問題の幅は大きく広がり、Pythonの柔軟性をさらに引き出すことができます。次に示すサンプルコードでは、記事全体の復習として階乗とフィボナッチの再帰処理をもう一度整理し、Python特有の書き方を確認しながら実践的な理解を深められるようになっています。

再帰処理のサンプルコードまとめ

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print("5の階乗:", factorial(5))
print("最初の10個のフィボナッチ数列:")
for i in range(10):
    print(fibonacci(i))