<一覧に戻る

部分問題の分割アプローチと再帰との違い

プログラミングにおいて、問題を解決するためのアプローチは多岐にわたります。特に「部分問題の分割アプローチ」と「再帰」は、問題解決において非常に重要なテクニックです。これら二つのアプローチは似ているように見えますが、実際には異なる概念です。この教材では、これらの違いを説明し、サンプルコードを通じて理解を深めていきます。

部分問題の分割アプローチ

部分問題の分割アプローチは、大きな問題を小さな問題に分割し、それぞれの問題を解決することで大きな問題を解決する方法です。このアプローチは、主に動的計画法（Dynamic Programming, DP）で使用されます。DPでは、同じ部分問題を何度も計算することを避けるため、計算結果を保存（メモ化）します。

例: フィボナッチ数列の計算

フィボナッチ数列は、次のように定義されます。 - F(0) = 0 - F(1) = 1 - F(n) = F(n-1) + F(n-2) (n >= 2)

この問題を部分問題の分割アプローチで解くと、次のようになります。

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

# 使用例
print(fibonacci(10))  # 出力: 55

コード解説

fibonacci関数は、引数nに対してフィボナッチ数を計算します。
memoという辞書を用いて、計算したフィボナッチ数を保存します。
すでに計算済みの値があれば、その値を返し、新たに計算する必要を無くします。

再帰

再帰は、関数が自分自身を呼び出す手法です。再帰を使用することで、問題をより簡潔に表現できますが、計算効率が悪くなる場合があります。特に、同じ計算を何度も行う場合は、パフォーマンスが低下します。

例: フィボナッチ数列の計算（再帰的アプローチ）

再帰を用いてフィボナッチ数列を計算する方法は次の通りです。

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

# 使用例
print(fibonacci_recursive(10))  # 出力: 55

コード解説

fibonacci_recursive関数は、フィボナッチ数を再帰的に計算します。
基本ケースとしてn=0とn=1を定義し、それ以外の場合には自分自身を呼び出して計算します。
この方法は簡潔ですが、nが大きくなると計算時間が指数的に増加します。