おいおい追加予定
こんなとき再帰使う可能性高いよ！
N、N-1などの状態で同じ処理を行いたいとき
https://atcoder.jp/contests/abc115/tasks/abc115_dループのネストを可変にしたいとき
https://atcoder.jp/contests/abc114/tasks/abc114_c
簡単な説明
- N、N-1などの状態で同じ処理を行いたいとき
そもそも再帰関数の定義のような部分でもある。N,N-1, ... , i , ... , 2, 1などを考えたとき、N番目でもi番目でも1番目でも同様の処理を行う。再帰関数に共通することであるが、終了条件を明確にすることが大切。
- ループのネストを可変にしたいとき
競技プログラミングの問題を解いていくと、ループのネストを可変にしたい時がある。例えば、入力が10の時2重ループ、100の時は3重ループを作成したいと言った時だ。for文のネストを最大長で動作するようにしたのち、フラグを作ると言った解決策もないことはない。しかし、応用が効きづらくなるので再帰を覚えた方が良いであろう。
まとめ
再帰の基本は類似状態の探索っぽいですね