現在Recursionに取り組んでいる。 そこで学んだことをメモする。
再帰処理
再帰処理とは、とある処理の中で、自分自身を呼び出す処理のこと。 例えば以下のような処理。
def sum(n): if n == 0: return 0 return sum(n-1) + n
これを実行すると以下のようになる。
result = sum(5) # result = 5 + 4 + 3 + 2 + 1 + 0 = 15
再帰処理を実装する際、漸化式が書けるかを確認すると良い。
例えば上記のsum()
関数は以下のような漸化式が書ける。
sum(0) = 0 sum(n) = sum(n-1) + n
このパターンを見抜けると、すんなり再帰処理を実装できる。