再帰関数

再帰は非常にシンプルでありながら、非常に強力な概念です。一度理解してしまえば、それなりに簡単な概念なのですが、残念ながら、その理解を得るためには、それなりの努力が必要です。

再帰関数を理解するために必要な例は、再帰の原理を明確に示しながら、その威力をほのめかし、その結果、再帰がなぜ魅力的な概念であるのかを示してくれるものです。しかしながら、今日の世の中では、そのような理想的な例とは、かけ離れた例がよく見かけられます。

最悪: 階乗計算😇

int factorial (int n)
{
    if (n <= 1)
        return 1;
    else
        return n * factorial(n-1);
}

単純な関数であり、何を行っているのか明白です。初学者にとって、再帰関数がどのようなものか把握するのにうってつけでしょう。
しかし、再帰関数にするメリットが全く見つかりません。少し考えれば、for文で同じことが出来ることに気が付きます。この例を出されてしまうと、再帰関数のコンセプト(ある意味)の理解がしづらいと考えます。

まあまあ: フィボナッチ数列🧐

int fibonacci (int n)
{
    if (n <= 1)
        return n;
    else
        return fibonacci(n-1) + fibonacci(n-2);
}

フィボナッチ数列は、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...のように、前の2つの数の和を次の数としていく数列です。

f(1) = f(2) = 1
f(n) = f(n-1) + f(n-2) [n>2]

という数式で表されるため、上記のような再帰的なプログラムで表現できるのは当然といえば当然です。しかし、この関数は大変非効率的であり、fibonacci(20)で呼び出すと答えを導くまでに、21891回の再帰的呼び出しを行ってしまいます。

count = 0

def fibonacci(n):
    global count
    count += 1
    if n == 0 or n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(20))
print(count)

10946
21891

フィボナッチ数列を求める再帰関数は、こちらの記事を参考にするとより良いアルゴリズムに改善可能です。つまり、フィボナッチ数列を再帰関数で求める例も、再帰関数の威力を理解するのには不向きです。
とは言っても、初学者にとって理解しやすいこのコードは、再帰関数の導入としては十分に最適だと考えます。

最適: ハノイの塔😊

/* hanoi - use recursion to solve towers of hanoi */
void hanoi (int height, int first, int temp, int final)
{
    if (height <= 0) return;
    hanoi (height-1, first, final, temp);
    printf ("Move disk %d from %d to %d.",
        height, first, final);
    hanoi (height-1, temp, first, final);
}

/* Print a solution for the towers with five disks */
int main()
{
    hanoi (5, 1, 2, 3);
}

ハノイの塔は、以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない

解は、次のように再帰的に考えることができる。塔を「一番下にある円盤」と「残りの円盤群」というように分けてみる。そして、まず「残りの円盤群」を移動させ、次に「一番下にある円盤」を移動し、その上にまた「残りの円盤群」を動かせばよい。

cf. ハノイの塔 - Wikipedia

ハノイの塔の解法において、非再帰的な解法はプログラムがより複雑になり、本当に正しい解法が表示されているかどうかを確認するのに非常に多くの労力を要することがわかるでしょう。そのため、ハノイの塔の再帰的解法は、再帰の原理を明確に示しながら、その威力をほのめかしている最適な例だと言えると考えます。

まとめ

初学者にいきなり再帰関数の最適な例として、ハノイの塔を紹介しても、かなり難しい問題なため理解できず、プログラミングへの苦手意識が高まってしまうでしょう。そこで、フィボナッチ数列などが再帰関数の例としてあげられることは問題だとは思いません。しかし、それだけで再帰関数を終わらせてしまうのは、再帰関数の威力・魅力があまり伝わらないためもったいないと考えます。そのため、ぜひとも、CSの教師や教材作成者には、ハノイの塔の話も織り交ぜて再帰関数の説明をしていただきたいです。

謝辞

この記事は、筆者Peter Raynhamさんの許可を得た上で、Examples of Recursion: The Good, the Bad, and the Sillyを参考に執筆しました。
Thank you for the interesting article and permission to translate.