女性向けエンジニアスクール
3秒でわかる
繰り返しや再帰を止めるための条件。再帰ではベースケースとも呼ばれ、これが無いとコールスタックを使い切ってプログラムが落ちます。
もう少し詳しく
どういうものか
終了条件は、繰り返し処理を終わらせる判定です。再帰関数では、自分自身を呼ばずに答えを直接返す最も小さい場合を指し、ベースケースとも呼ばれます。ループでは、カウンタが上限に達した、探索対象が空になった、といった条件がこれにあたります。
再帰関数は、終了条件と、問題を一段小さくして自分を呼ぶ部分の2つで構成されます。どちらが欠けても正しく動きません。
なぜ必要か
再帰は関数呼び出しのたびに、戻り先や引数をコールスタックへ積みます。終了条件が無いと積み続け、領域を使い切って RecursionError や StackOverflowError で落ちます。ループの場合は落ちすらせず、CPUを占有したまま止まらなくなります。終了条件は、処理が有限回で終わることを保証する部分です。
具体例
def factorial(n):
if n <= 1: # 終了条件。ここで再帰が止まる
return 1
return n * factorial(n - 1) # 引数を1つ小さくして呼ぶ
print(factorial(5)) # 120n <= 1 を消すと、n が 0、-1、-2 と際限なく下がり続けて停止しません。n == 1 と書くのも危険で、factorial(0) や負の数を渡すと条件に触れずに落ちます。等号だけでなく不等号で受け止めておくのが定石です。
二分探索のように、範囲が空になったことを終了条件にする形もあります。
def binary_search(arr, target, low, high):
if low > high: # 範囲が尽きたら見つからない
return -1
mid = (low + high) // 2
if arr[mid] == target: # 見つかった場合も終了条件
return mid
if arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
return binary_search(arr, target, low, mid - 1)つまずきやすいところ
終了条件は書いたのに、引数が小さくなっていないパターンが最も多い誤りです。上の二分探索で mid + 1 を mid と書くと、範囲がいつまでも縮まらず永久に呼び続けます。終了条件と、条件へ近づく変化は必ず対で確認します。
浮動小数点数を等値で判定するのも危険です。while x != 0.0 のような書き方は、丸め誤差でぴったり0にならず止まらないことがあります。while abs(x) > 1e-9 のように幅を持たせます。
覚え方
再帰は階段を降りる動作です。一段ずつ降りる処理と、地面に着いたら降りるのをやめる判断の両方が要ります。終了条件は地面にあたる部分で、これが無い階段は底が抜けています。
