Pythonで再帰関数を理解する
プログラミングをしていれば、「再帰」や「再帰関数」という手法をよく聞くものの、あまり使ってこなかったこともあり、使う場面などについてあまり考えてきませんでした。
ある程度、再帰関数について調べたため、簡単な例から実際に使う例などを交えて再帰関数を解説していきます。
再帰関数とは
再帰関数とは、自分自身を呼びだす関数のことです。
大きな問題を小さな問題に分割して解決する分割統治法で使われる手法です。
大きな問題も、問題の領域を小さくしていけば、問題が解きやすくなります。再帰関数はこういった問題を解くために使われます。
簡単な例
上記の説明を読んでも、何を言っているんだろうと思った方も多いはずなので、実際に簡単な例をご紹介します。
「1からnまでの自然数の和を返す関数」を作成してみます。すると以下のような実装になるはずです。
至ってシンプルな実装ですが、これでは再帰関数を用いていません。
def sum(n):
res = 0
for i in range(n+1):
res += i
return resそれでは実際に「再帰関数」を用いて実装してみると、以下のようになります。関数内で、再度sum()関数が呼び出されているため、自分自身を再度呼び出していることがわかります。
def sum(n):
if n <= 0:
return n
return n + sum(n-1)実際に上記の関数を使用してみると、以下のように自然数の和が返るはずです。
print(sum(10))
# 55中身を見てみると、nが0以下になるまで、nから1を引いたn-1を引数に入れてsum関数を呼び出しています。返ってきた結果をnに足しています。
これはつまり、以下のことをやっているのと同じになります。
# sum(10)とした場合
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
= 55
少し複雑な問題を解いてみる
上記の例では簡単すぎて、実際に使うのには想像がつきません。そこで以下のような少し複雑な問題を解くのに、再帰関数は役立ちます。
以下のjsonから a,b,c,d,e などの文字部分(str型)を取り出す
data = [
"a",
["b", 1, [[["c", 2], 3], 4], "d"],
["e"]
]上記のような複雑なjsonデータがあったとして、どのように文字(str型)を取り出せば良いのでしょうか。普通に実装してみると以下のような感じになると思います。
data = [
"a",
["b", 1, [[["c", 2], 3], 4], "d"],
["e"]
]
res = []
for arg in data:
if isinstance(arg, str):
res.append(arg)
if isinstance(arg, list):
for v in arg:
if isinstance(v, str):
res.append(v)
......
......
......
......
# ネスト(深く)していく上記のような方法ではインデントが徐々に広がっていきますし、何より渡されるリストの階層が増えていく事に、for文を回していかなければいけません。
こういった複雑な処理に再帰関数が役立ちます。以下の用に実装しましょう。
・文字(str型)かどうかを判定して、文字(str型)の場合はリストresに追加
・list型の場合はfor文で回して、再帰的に関数を呼び出す
data = [
"a",
["b", 1, [[["c", 2], 3], 4], "d"],
["e"]
]
def get_str(arg):
result =[]
if isinstance(arg, str):
result.append(arg)
if isinstance(arg, list):
for item in arg:
res = get_str(item)
result += res
return result
if __name__ == "__main__":
print(get_str(data))さきほどに比べればかなりスッキリとした形になりました。これなら渡されるdata(list型)の階層がどんなに深くなっても処理が可能になります。
上記の処理はlist型が出る度に、再帰的に関数に値を渡していることがわかります。
このようにより多くの条件が必要な複雑な問題などは再帰関数などを使うのがよいのかもしれません。
正直言えば、自分もまだあまり意識的に書いたことがそんなに多くないため、徐々に使えそうなところを書き換えている感じです。
ソースコードや資料等は以下を参考にしました。(ソースに関してはかなりパクらせていただきました・・・)
参考資料