def ussee(i):
if i <= 0:
return "わ"
else:
return f"うっせぇ{ussee(i-1)}"
print("はぁ?")
print(ussee(3))
# はぁ?
# うっせぇうっせぇうっせぇわ
関数ussee(i)
は、8行目のように呼び出すとその処理の中で5行目のように自身を呼び出します。
このように処理の中で自身を呼び出すことを再帰呼び出しといい、再帰呼び出しを行う関数を再帰関数といいます。
再帰関数に終わりを設定しないと無限ループになるため大抵は自身を呼び出さないタイミング、すなわち再帰呼び出しの「終わり」を設定します。
ussee(i)
だと以下の部分が「終わり」に該当します。
if i <= 0:
return "わ"
そういった終わりの部分は基底部といいます。
この例では引数i
が呼び出しごとに1減算され、0以下になったときに再帰呼び出しが終わります。
ussee(i)
に0を指定した場合、以下が出力されます。
print("はぁ?")
print(ussee(0))
# はぁ?
# わ
わ (← かわいい)
ussee(100)
を呼び出すとどうなるでしょう。
print("はぁ?")
print(ussee(100))
# はぁ?
# うっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇうっせぇわ
ではussee(1000000000)
ではどうでしょう。
RecursionError: maximum recursion depth exceeded in comparison
再帰呼び出しが多くなりすぎると、Pythonは途中でエラーを出して止めてくれます。
関数は呼び出しごとにメモリに呼び出し情報を蓄積するため、特に再帰関数の場合は制限をかけないと大量に呼び出し情報を蓄積してしまいます。(後述する不具合の原因となります)
以下のコードでPythonはどれくらいなら許してくれるのか確認することができます。
import sys
print(sys.getrecursionlimit())
# 例: 1000
1000回までなら大丈夫だそうです。
以下のコードで制限を変更することもできます。
sys.setrecursionlimit(100000)
制限を緩くしすぎた場合、それは大量の呼び出し情報の蓄積を許すことになるため今度はメモリ自体の許容範囲を超えてしまうスタックオーバーフローという不具合が発生し、プログラムはクラッシュします。
import sys
sys.setrecursionlimit(100000)
def ussee(i):
if i <= 0:
return "わ"
else:
return f"うっせぇ{ussee(i-1)}"
print("はぁ?")
print(ussee(100000))
print("あ")
この場合、最初のはぁ?
しか出力されません。異常エラーのため、クラッシュについては何も出力してくれません。
こういった呼び出し情報を大量に蓄積してしまう問題を解決するため、「再帰関数はループしている」という性質をもとに
呼び出し情報を蓄積しないようなプログラムに書き換える末尾呼び出し最適化という処置を施すプログラミング言語も存在します。
再帰関数は最初はわかりづらかったり、メモリ上の制限があったりなど注意することはありますが、実世界の問題解決において「再帰的な構造」という発想は問題の構造を把握する上で非常に重要な考え方です。また、そういう文脈で最適化という処置が存在することも踏まえると、再帰関数をおさえておく価値は大きいように思います。
わ
が可愛いかったので つい出来心で書いてしまいました。お力になれたら幸いです。
追記: 本当にくだらないですがある発見をしましたので共有します。
def ussee(i):
if i <= 0:
return "わ"
else:
return f"うっせぇ{ussee(i-1)}"
social_rules = ["最近の流行は当然の把握", "経済の動向も通勤時チェック", "純情な精神で入社しワーク"]
print("はぁ?")
print(ussee(len(social_rules)))
# はぁ?
# うっせぇうっせぇうっせぇわ
def ussee(rules):
if not rules:
return "わ"
else:
rules.pop()
return f"うっせぇ{ussee(rules)}"
social_rules = ["最近の流行は当然の把握", "経済の動向も通勤時チェック", "純情な精神で入社しワーク"]
print("はぁ?")
print(ussee(social_rules))
# はぁ?
# うっせぇうっせぇうっせぇわ
こちらの変更ではpop
の戻り値の使い捨ても相まって詩的なコードになりました。