【第8回】再帰関数

再帰関数とは

再帰関数とは、自分自身を呼び出す関数のことを指します。

再帰関数を終了するための条件(ベースケース)と、関数が自分自身を呼び出す再帰的な部分(再帰ステップ)の2つを適切に構築することがポイントです！

例として、 $1$ から整数 $n$ の総和を求めるプログラムを示します。

#include <bits/stdc++.h>
using namespace std;

int sum(int n) {
    // ベースケース
    if (n == 1)
        return 1;

    // 再帰ステップ
    else
        return n + sum(n - 1);
}

int main() {
    int n;
    cin >> n;

    cout << sum(n) << endl;

    return 0;
}

例えば、 $n = 10$ としたら、 $sum(n) = 55$ となります。

問題

再帰関数を使って、問題を解いてみよう！

整数 $n$ の階乗を求めてください。

factorial.cpp

#include <bits/stdc++.h>
using namespace std;

int factorial(int n) {
    // ベースケース
    if (/*(1)*/)
        return 1;

    // 再帰ステップ
    else
        return /*(2)*/;
}

int main() {
    int n;
    cin >> n;

    cout << "n : " << n << " , ";
    cout << "n! : " << factorial(n) << endl;

    return 0;
}

出力例です。

n : 5 , n! : 120

n : 10 , n! : 3628800

解答例

#include <bits/stdc++.h>
using namespace std;

int factorial(int n) {
    // ベースケース
    if (n == 0)
        return 1;
    
    // 再帰ステップ
    else
        return n * factorial(n - 1);
}

int main() {
    int n; 
    cin >> n;

    cout << "n : " << n << " , ";
    cout << "n! : " << factorial(n) << endl;

    return 0;
}

整数 $a$ と $b$ の最大公約数を求めてください。

2つの整数の最大公約数を求めるアルゴリズムであるユークリッドの互除法を用います！ユークリッドの互除法では、2つの整数が $a, b$ のとき、 $a$ を $b$ で割った余りを $r$ とすれば、「 $a$ と $b$ の最大公約数は、 $b$ と $r$ の最大公約数に等しい」という性質を利用します。

mygcd.cpp

#include <bits/stdc++.h>
using namespace std;

int mygcd(int a, int b) {
    // ベースケース
    if (/*(1)*/)
        return /*(2)*/;

    // 再帰ステップ
    else
        return /*(3)*/;
}

int main() {
    int a, b; 
    cin >> a >> b;

    cout << "a : "<< a << endl << "b : " << b << endl;
    cout << "gcd : " << mygcd(a, b) << endl;

    return 0;
}

$a = 24,b = 18$ としたときの出力例です。

a : 24
b : 18
gcd : 6

ヒント

余りが出なかった時に割った値がその2つの整数の最大公約数
$gcd(a,b) = gcd(b,r)$

解答例

ベースケースでは、 $b = 0$ になった(割り切れた)時、 $a$ が最大公約数となるので、 $a$ の値を返します。 $a$ を $b$ で割った余りを $r$ とすると、( $a$ と $b$ の最大公約数) = ( $b$ と $r$ の最大公約数)となるので、これを再帰ステップとします。

#include <bits/stdc++.h>
using namespace std;

int mygcd(int a, int b) {
    // ベースケース
    if (b == 0)
        return a;

    // 再帰ステップ
    else
        return mygcd(b, a % b);
}

int main() {
    int a, b; 
    cin >> a >> b;

    cout << "a : "<< a << endl << "b : " << b << endl;
    cout << "gcd : " << mygcd(a, b) << endl;

    return 0;
}

手元で色々な数値を入れて確かめてみて！

フィボナッチ数列の $n$ 番目の数を求めてください。

フィボナッチ数列は、前の2つの数の和が、次の数になる数列のことです。次に示す数列がフィボナッチ数列です。 $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...$

fibonacci.cpp

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n) {
    // ベースケース
    if (/*(1)*/)
        return 0;
    if (/*(2)*/)
        return 1;
    
    // 再帰ステップ
    else
        return /*(3)*/;
}

int main() {
    int n;
    cin >> n;

    cout << "n : " << n << " , ";
    cout << "fibonacci : " << fibonacci(n) << endl;

    return 0;
}

出力例です。

n : 0 , fibonacci : 0
n : 1 , fibonacci : 1
n : 9 , fibonacci : 34
n : 20 , fibonacci : 6765

解答例

ベースケースとして、 $n = 0$ の時 $0$ を、 $n = 1$ の時 $1$ を返しています。再帰ステップで、 $n-1$ (1つ前)と $n-2$ (2つ前)を呼び出しています。

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n) {
    // ベースケース
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    
    // 再帰ステップ
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    cin >> n;

    cout << "n : " << n << " , ";
    cout << "fibonacci : " << fibonacci(n) << endl;

    return 0;
}

メモ化再帰

同じ引数で再帰呼び出しが何度も行われることがあるため、計算量が膨大になり効率が悪くなってしまう場合があります。

例えば、フィボナッチ数列の再帰関数の呼び出す状況を表すコードを $n = 6$ で実行してみます。

#include <bits/stdc++.h>
using namespace std;

int fibonacci(int n) {
    printf("fibonacci(%d)が呼び出されました。\n",n);

    // ベースケース
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    
    // 再帰ステップ
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    cin >> n;

    int ans = fibonacci(n);

    printf("\nfibonacci(%d) = %d\n", n, ans);

    return 0;
}

実行結果は以下のようになります。一般に計算量は $\Omicron(2^n)$ かかってしまします。

fibonacci(6)が呼び出されました。
fibonacci(5)が呼び出されました。
fibonacci(4)が呼び出されました。
fibonacci(3)が呼び出されました。
fibonacci(2)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(0)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(2)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(0)が呼び出されました。
fibonacci(3)が呼び出されました。
fibonacci(2)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(0)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(4)が呼び出されました。
fibonacci(3)が呼び出されました。
fibonacci(2)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(0)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(2)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(0)が呼び出されました。

fibonacci(6) = 8

この問題を解決する方法として、メモ化があります。メモ化とは、1度計算した結果を保存しておくことで、同じ計算が再度発生するときに、再計算をすることなく保存されている計算結果を再利用することで、効率的に処理する手法です。この手法を使うことで計算量を $\Omicron(n)$ に減らすことが出来ます。

C++では、メモ化用の配列を用意します。

#include <bits/stdc++.h>
using namespace std;


int fibonacci(int n, vector<int> &memo) {
    printf("fibonacci(%d)が呼び出されました。\n",n);

    // メモに既に保存している場合
    if (memo[n] != -1)
        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];
}

int main() {
    int n;
    cin >> n;

    // メモの初期化
    vector<int> memo(n + 1, -1);  // 要素は全て-1で初期化

    int ans = fibonacci(n, memo);
    printf("\nfibonacci(%d) = %d\n", n, ans);

    return 0;
}

先程と同様に $n = 6$ で実行してみると、結果は以下の通りになります。呼び出し回数を減らすことが出来ました！

fibonacci(6)が呼び出されました。
fibonacci(5)が呼び出されました。
fibonacci(4)が呼び出されました。
fibonacci(3)が呼び出されました。
fibonacci(2)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(0)が呼び出されました。
fibonacci(1)が呼び出されました。
fibonacci(2)が呼び出されました。
fibonacci(3)が呼び出されました。
fibonacci(4)が呼び出されました。

fibonacci(6) = 8

【第8回】再帰関数

再帰関数とは

問題

メモ化再帰

問題集

【第7回】計算量

【第9回】順列全探索と二分探索