みなさんこんにちは、IT初心者のうえはらです。

最近、paizaというサイトのスキルチェックにハマっているのですが、どうしてもやりかたがわからない問題があるんですね！

迷路問題など。

力ずくで解こうとしても、どうしても行き詰ってしまう。

独学でプログラミングしているので、アルゴリズムがわかりません。

そこで、一度paizaから離れて、アルゴリズム系の勉強をしてみようと張り切ってます。

色々と、調べていて、再帰関数についてもいまいちわからなかったので、まずは、再帰関数について調べてみました。

再帰関数とは?

Wikipediaを検索すると、再帰・再帰呼び出しとでています。

要約すると自分自身で自分自身をということのようです。

なんのこっちゃ？

わかるようでわからないので、例としてよく挙げられている階乗計算を実際に手を動かしてやって見ます。

階乗計算

階乗の詳しい説明はWikipediaなどを参照下さい。

N！はNから１までの全ての整数の積ということですね。

５！＝5×4×3×2×1＝120　です。

これをpythonでかくとこうなります。

def fact(N):
    if N == 1:
        return 1
    return N * fact(N-1)

print(fact(5))

偉そうに書いていますが、下記を参考にしました。

お気楽 Python プログラミング入門

何がわからないって?　何かがわからないんですよね～。

プログラムって上から下にif文があったら条件分岐だったり、独学ではこんなもんですよね～。

まぁ、returnはなんとなくわかりますよ。もし、Nが1だったら「１」を返すと！

じゃぁ、N×fact(N-1)って！！！

これにつまづいたので、紐解いてみます。

まず、1行目

def fact(N):

これは「fact(N)」という関数を定義しています。

次は6行目

print(fact(5))

で「fact(N)」関数にN=5を代入して、return で戻ってきた値を、print で出力しています。

はい、やっときました「fact(N)」

こんかいはN=5なので、「fact(5)」ですね。

N＝＝1じゃないので、

return 5 * fact(5-1)

となります。

５×fact(4)を返すってどういうこと？　ですよね。

でも、ここで深く考えません。

「fact(4)」をやるんです！

def fact(N):
    if N == 1:
        return 1
    return N * fact(N-1)

print(fact(4))

みたいな感じで、N==1じゃないので、

return 4 * fact(4-1)

同じように、fact(3)は

return 3 * fact(3-1)

同じように、fact(2)は

return 2 * fact(2-1)

そして「fact(1)」！

def fact(N):
    if N == 1:
        return 1
    return N * fact(N-1)

print(fact(1))

N==1なので、

return 1

やっと、「１」が帰ります！！！

長かった～～～。

今度は逆に考えて、

return 2 * fact(2-1)  →  return 2 * 1  →  return 2

return 3 * fact(3-1)  →  return 3 * 2  →  return 6

return 4 * fact(4-1)  →  return 4 * 6  →  return 24

最後に「fact(5)」！

return 5 * fact(5-1)  →  return 5 * 24 → return 120

はぁ、やっと帰ってきた！というところでしょうか?

これで、「120」が帰されました。

まとめ

いかがでしたか？

なんとなくわかっていただけました？

実際に、手を動かしてみることで、プログラムの流れはつかめると思います。

でも、再帰関数を利用する場面がよくわからんなぁ～