数学から見る再帰関数

Likes16

こんにちは。ほまれちゃんと申します。

皆さん、再帰関数、使ってますか？

「なんか難しそう」

という声をよく聞くように思います。

初心者エンジニアの登竜門と言われる(?)再帰関数ですが、この記事は題名の通り、数学的な視点から解説をしたいと思います。

少しでも理解の助けになったら嬉しいです。

この記事ではPythonとHaskellにおける実装を紹介しています。

Python、Haskellに関する知識はなくても読めるよう心がけているので、これらを知らない方もご安心ください。

導入

まず、再帰関数の定義を確認したいと思います。

再帰呼出し（さいきよびだし、英: recursive call）は、プログラミング技法の一つである。^[1]

(出典: Wikipedia)

プログラミング技法の一つみたいです。

手続きや関数といった概念をもつプログラミング言語では、ある手続き中で再びその手続き自身を呼び出すことを認める場合が多い。これを再帰呼出しといい、階乗計算やフィボナッチ数列のように、本来再帰的な構造をもつアルゴリズム（再帰的アルゴリズム）を記述するのに適している。

Wikipediaの例にも上がっているので、

階乗
フィボナッチ数列

この2つを主な例に解説していきたいと思います。

階乗(factorial)

階乗がなにかわからない方もいるかも知れないので、はじめに簡単な解説をします。

数学において非負整数 nの階乗（かいじょう、英: factorial）n ! は、1 から n までのすべての整数の積である。

(出典: Wikipedia)

例えば、

5の階乗 → $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
10の階乗 → $10! = 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 3628800$

まず、Pythonで実装してみます。

def fact(n):
    ans = 1 # 答えになる変数を0で初期化
    for m in range(1, n + 1): # 1からnまでループ
        ans *= m # 答えにかけていく
    return ans

print(fact(5)) # => 120
print(fact(10)) # => 3628800

単純なので理解しやすいかと思います。

「これがどう再帰関数と関係があるの…？」

とお思いの方も多いかもしれません。

ここで、少し数学をします。

高校生の時に学んだ漸化式というものを覚えていますでしょうか？

ここでもまた、Wikipediaで定義を確認します。

数学における漸化式（ぜんかしき、英: recurrence relation; 再帰関係式）は、各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式である。

(出典: Wikipedia)

ここで階乗の定義を少し変形します。

nの階乗、 「nとn-1の階乗との積」 と考えることはできないでしょうか？

つまり、

6! = 6 \times 5! = 6 \times 120 = 720

みたいな。勘の良い方は気づかれたかもしれませんが、これが 「各項がそれ以前の項の関数として定まる」 ということです。すなわち、

\begin{aligned} 6! & = 6 \times 5! \\ & = 6 \times 5 \times 4! \\ & = 6 \times 5 \times 4 \times 3! \\ & = 6 \times 5 \times 4 \times 3 \times 2! \\ & = 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\ & = 720 \end{aligned}

という展開ができるのです。このとき、階乗の中で階乗が呼び出されていますよね？

これが世に聞く 「再帰関数」 です。

早速ソースコードを、と言いたいところですが、もう少し理解を深めてからにしたいと思います。

先程出した漸化式で階乗を表してみましょう。

まず日本語で階乗の定義を丁寧に確認します。

ここでは非負整数の階乗についてのみ考え、ソースコード内においても適切な引数ガードができていない可能性があります。くれぐれも本番コードに使用しないようにしてください。

nが1の時 → 1
nが1でない時(n+1の時) → n+1とnの階乗の積

これを数学的な漸化式に落とし込みます。 $a_n$ をnの階乗と置くと、

\begin{aligned}a_1 & = 1 \\ a_{n+1} & = (n + 1) \times a_n\end{aligned}

となります。

プログラムに直接落とし込むには少し都合が悪いので、少し数学的に正しくない変形をします。

\begin{aligned}a_1 & = 1 \\ a_n & = n \times a_{n - 1}\end{aligned}

ここで、 $a_1 = 1$ は初期値といい、すべての非負整数nに対する階乗はすべてこの値に帰結します。

$a_1$ の定義がないとnが負の方向に向かって無限にループしてしまい、求める階乗の値が得られません。

漸化式が作れたので、これをHaskellプログラムに落とし込みたいと思います。

fact :: Int -> Int
fact 1 = 1 -- 初期値
fact n = n * fact (n - 1)

main :: IO ()
main = do
    print (fact 5) -- => 120
    print (fact 10) -- => 3628800

Haskellをご存知でない方も多いかもしれませんが、こんな感じに数学の漸化式と似た形で関数の定義ができ、直感的、視覚的に理解できるのでHaskellを使いたいと思います。

このコードの動作を追うと、こうなっています。

fact 5
5 * fact 4
5 * 4 * fact 3
5 * 4 * 3 * fact 2
5 * 4 * 3 * 2 * fact 1
5 * 4 * 3 * 2 * 1 ←ここで初期値が展開される

ね？簡単でしょ？

また、Pythonでも同様に実装してみましょう

def fact(n):
    if n == 1:
        # これが初期値
        return 1
    else:
        return n * fact(n - 1)
    
print(fact(5)) # => 120
print(fact(10)) # => 3628800

やっていることは至って単純です。

どうですか？意外と簡単じゃないですか？

では、2つ目のお題に移ります。

フィボナッチ数列

先ほどと同様、まずは定義を確認します。

フィボナッチ数列（フィボナッチすうれつ、（英: Fibonacci sequence） (Fn) は、次の漸化式で定義される

$\begin{aligned}F_0 & = 1 \\ F_1 & = 1 \\ F_{n+2} & = F_n + F_{n+1} (n \ge 0)\end{aligned}$

(出典: Wikipedia)

先ほどと少し形が違うので、添字をずらしつつ先ほど同様変形をしてみましょう。

\begin{aligned}F_1 & = 1 \\ F_2 & = 1 \\ F_n & = F_{n - 1} + F_{n - 2}\end{aligned}

これを日本語で説明すると、

前の2つの項の和を並べた数列

ということになります。

$F_5$ の計算過程を見てみると、

\begin{aligned}F_5 & = F_4 + F_3 \\ & = (F_3 + F_2) + (F_2 + F_1) \\ & = ((F_2 + F_1) + F_2) + F_2 + F_1 \\ & = ((1 + 1) + 1) + 1 + 1 \\ & = 5\end{aligned}

となり、無事計算できていることがわかります。

では、Haskellで書いてみます

f :: Int -> Int
f 1 = 1
f 2 = 1
f n = f (n - 1) + f (n - 2)

main :: IO ()
main = do
    print (f 5) -- => 5

続いてPythonも見てみましょう

def f(n):
    if n == 1 or n == 2:
        # 初期値
        return 1
    else:
        return f(n - 1) + f(n - 2)
    
print(f(5)) # => 5

これらの関数の動作は

f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(2) + f(2) + f(1)
1 + 1 + 1 + 1 + 1
5

となっています。

あとがき

どうでしょうか？「意外と簡単だな。」って思っていただけましたか？

再帰関数を活用できる場面は限られているかもしれませんが、「使えそう！」となったらぜひ使ってみてください。

Stack overflowなどに十分気をつけて実装してください！

それでは〜🍆

脚注

「英」に英語のページがリンクされているのに驚きましたが、関係ないのでスルーします ↩︎