再帰関数には2種類ある。
先頭再起：関数の先頭で再起が起こる
末尾再帰：すべての処理を行ってから再起が起こる
どちらも上から下までを往復する。
末尾再帰は上で処理したデータを下に渡した、下から処理したデータが返ってくる。
先頭再起は上では下を呼び出すだけで、下から処理したデータが返ってくる。
先頭再起の方が渡すデータが少なく優れている。
ひたすらスタックに積んでいって積み終わったら上から取ってくイメージ。
再帰関数の書き方は
def 再帰関数
終了条件
再起呼び出し
処理
戻り値
end
一番下の条件を考える。
その1個上を考えて合わせる。
あとは流れに従えば再帰関数ができる。
