Python再帰入門：初心者でもわかる再帰関数の基本と使い方

Pythonで再帰を使う方法

Pythonの再帰は、初心者にとって難しく感じられるトピックの一つです。しかし、「再帰は難しい」という思い込みを、まず定義から払拭しましょう。再帰とは、関数が自分自身を呼び出すプログラミング手法のことです。

シンプルに聞こえますよね。コツをつかめば、再帰は決して難しい概念ではありません。

このチュートリアルでは、再帰とは何か、そしてどのように動作するのかを解説します。階乗計算を例に、再帰プログラミングの始め方を一緒に見ていきましょう。

再帰とは何か？

再帰とは、あるものをそれ自身を使って定義することです。

再帰関数は、自分自身を繰り返し呼び出すことで問題を解決します。この動作はPythonをはじめ、多くの主要なプログラミング言語でサポートされており、コンピュータサイエンスやデータサイエンスにおいて重要な概念となっています。

再帰が特に役立つのは、問題をより小さな問題に分解し、そのすべてに同じ式を適用できる場合です。この種の問題は「再帰的アルゴリズム」と呼ばれます。解法の鍵は、まさに名前の中にあるのです！

反復処理と再帰処理の違い

アルゴリズムを解く方法には、「反復（イテレーション）」と「再帰」の2つがあります。

反復的な解法は「強力だが美しくない」と言われることがあります。目的は達成できますが、必ずしも最もエレガントな方法とは言えません。再帰的アルゴリズムを正しく理解するには、まず反復関数について知っておく必要があります。

反復関数とは、ループを使って問題を解く関数です。ループ内のコードを、ループが完了するまで実行し続けます。一方、再帰関数は、問題をより小さな部分に分解し、それぞれの部分を自分自身を呼び出すことで解決します。

階乗：反復処理の例

階乗は、再帰と反復的な考え方の違いを示すのに適した題材です。数学における階乗とは、ある数とそれ以下のすべての正の整数を掛け合わせたものです。

5の階乗は 5 × 4 × 3 × 2 × 1 に等しく、2の階乗は 2 × 1 に等しくなります。

階乗を計算するために、次のような反復関数を書くことができます。

def factorial(number):
    total = 1
    for n in range(1, number + 1):
        total = total * n
    return total

この関数はforループを使って、1から指定した数値+1までの範囲のすべての数値を順番に処理します。各反復で、ループが処理中の数値をtotalに掛けていきます。それでは、この関数を呼び出して階乗を求めてみましょう。

answer = factorial(4)
print(answer)

このコードは「24」を返します。この結果に至るまで、コード内部では次のような計算が行われています。

• 1 × 1 = 1
• 1 × 2 = 2
• 2 × 3 = 6
• 6 × 4 = 24

ご覧のとおり、このコードは4より小さいすべての数値と、4自身を掛け合わせています。

このコードは正しく機能します。ただ、もう少しエレガントに書ける余地があります。そこで登場するのが再帰関数です。

階乗：再帰の例

次に、階乗を計算する再帰関数を書いてみましょう。新しいPythonファイルを作成して、次のコードを貼り付けてください。

def factorial(number):
    if number == 1:
        return 1
    else:
        return (number * factorial(number - 1))

このコードは再帰的なアプローチを使用しています。関数が実行されると、まずif文が評価されます。if文は、関数に渡された数値が1と等しいかどうかをチェックします。等しければ関数は1を返し、そうでなければその数値の階乗が計算されます。

この計算は、関数に渡された数値に、その前の数値の階乗を掛けることで行われます。関数は「number」が1になるまで何度も呼び出され、呼び出されるたびに「number」の値は1ずつ減っていきます。

それでは、数値4で実際に試してみましょう。

answer = factorial(4)
print(answer)

答えとして24が返されました。前の例と同じ結果であり、正しい答えです。私たちはこの問題を反復処理ではなく、再帰によって解いたのです。

まだ少しピンとこないという方のために、もう一つ別の再帰の例を見てみましょう。

フィボナッチ数列での再帰

フィボナッチ数列は、各数値が直前の2つの数値の合計となる数列です。この数列は 0, 1, 1, 2, 3, 5, 8, 13… と続いていきます。

この数列は、2つの数値を足して次の数値を求めるため、再帰に理想的な題材です。

Pythonファイルを開いて、次のコードを貼り付けてください。

def fibonacci(number):
    if number <= 1:
        return number
    else:
        return(fibonacci(number - 1) + fibonacci(number - 2))

このコードは、「number」が1より大きい場合に、直前の2つの数値の合計を計算します。そうでなければ「number」をそのまま返します。それでは、関数を呼び出してみましょう。

executions = 5

print("Fibonacci Sequence:")
for number in range(executions):
    print(fibonacci(number))

変数executionsは、フィボナッチ数列のうちいくつの数値を計算したいかを管理します。これを使ってforループを作成し、0から「executions」の値までの範囲の各数値に対してfibonacci()関数を呼び出します。

forループが始まる前に、コンソールに「Fibonacci Sequence:」と出力します。この例では、forループは次のように実行されます。

fibonacci(0)
fibonacci(1)
fibonacci(2)
fibonacci(3)
fibonacci(4)

コード全体を実行して、結果を確認してみましょう。

Fibonacci Sequence:
0
1
1
2
3

このコードは、フィボナッチ数列の最初の5つの数値を計算しました。「executions」の値を増やせば、さらに多くの数値を計算することも可能です。

再帰の深さと基底条件

再帰関数には必ず基底条件（ベースケース）が必要です。これは、特定の条件が満たされた時点で再帰を停止させるための条件です。基底条件がないと、無限ループが発生してしまいます。

また、デフォルト設定では、再帰関数は最大1,000回までしか自分自身を実行できません。この上限に達すると、次のようなエラーが表示されます。

RecursionError: maximum recursion depth exceeded

先ほどのフィボナッチプログラムにおける基底条件は、次の部分です。

...
if number <= 1:
        return number
...

この条件は、フィボナッチプログラム内の「number」の値が1以下であるかどうかをチェックします。1以下であれば「number」の値を返し、そうでなければ再帰関数が起動します。

なぜ再帰を使うべきなのか？

反復関数ではなく再帰を使うメリットは何でしょうか？技術的には、どちらの方法でも同じ結果を得られます。再帰の最大の利点は、コードが読みやすいことです。

再帰関数を見れば、問題の答えが「問題を小さな部分に分解すること」にあるのが一目でわかります。反復ループの方が高速な場合もありますが、可読性の高さから再帰関数が好まれることが多いのです。

さらに、再帰関数は読みやすい分だけ、保守やデバッグも容易になります。これは、理解が難しい複雑なアルゴリズムを扱う際に特に大きなメリットとなります。

まとめ

再帰関数とは、問題の解決策を見つけるために自分自身を呼び出す関数のことです。

再帰関数は問題を複数の部分に分解し、反復ごとに問題の一部を解決していきます。階乗やフィボナッチ数列の計算をはじめ、さまざまなアルゴリズムで活用されている強力な手法です。

これで、あなたもPythonで再帰関数を使い始める準備が整いました！