再帰関数の話
再帰関数を最近AtCoderの問題で使う機会があったのですこし解説します。
再帰関数とは何か？
再帰関数(recursive function)とは、自分自身を呼び出す(recursive call)関数のことです。
以下は再帰関数の例によく用いられる、自然数の和を返す関数です。
def sum(num):
if num < 0:
return num
return num + sum(n - 1)
sum(10) # 55が返るsum()関数の処理内でsum()関数が再び呼ばれています。
ポイントは2点あります。
return num + sum(num - 1)まずここで、再び呼ばれたsum()関数に渡される値が変化していることが重要です。
今回の例ではグローバル変数を参照していないので、実行時に渡される値だけが処理内容を決めます。
仮に再び呼ばれたsum()関数が、1度目に呼ばれたときと全く同じ処理を行うのであれば必ず無限ループに陥ります。
if num < 0:
return numそれに加えて、このように再帰関数が呼ばれずに終了する経路が必要になります。
これもない場合は必ず無限ループに陥ります。
再帰関数の使いどころ
再帰関数の何が便利なのか？どのようなケースで使うのか？
まだ解説するほど深い知識がないのですがここをよむとだいたいわかります。
実践した例
AtCoderの競プロ典型90問において、いい感じに使う機会があったので置いておきます。
002 - Encyclopedia of Parentheses（★3）
num = int(input())
r = ')'
l = '('
arr = []
def recursive(str_):
global count
global arr
if len(str_) == num:
arr.append(str_)
if str_.count(l) < num/2:
recursive(str_ + l)
if str_.count(r) < str_.count(l):
recursive(str_ + r)
if num%2 == 1:
print('')
else:
recursive('')
arr.sort()
for str_ in arr:
print(str_)bit全探索で解いている例が多かったですが、こちらの方が計算量も少なくシンプルに解けているかと思います。
おわり
もっと色々おもしろい例があるので気が向いたら書き足します。
自然界にも再帰的な処理は色々あると思います。自己複製する生物の細胞も再帰関数みたいなもんですね。
オワリ