再帰関数とは？
再帰関数とは、関数の中からその関数自身を呼び出すような処理を行う関数のこと。
必ず終点が必要で、問題を徐々に単純化しないといけない。
再帰呼び出しを行うと、関数を呼び出すたびに引数やローカル変数がメモリを確保する。
再帰関数をいつ使うか？
1つ処理すると、残りの処理対象が増えたりする。
しかも増えた文は、元の構造が似ている。
場合につかうらしいです。
Tree構造のデータをたどるような場合等。(マージソート,クイックソート)
具体例 : 細胞分裂
1匹の細胞が一度に2匹に分裂するした結果を出力するプログラムを、ループと再帰関数を用いて書いてみます。
ループ
def cell_divison_loop(cell)
loop {
break if cell.length > 100
cell = cell * 2
}
return cell
end
p cell_divison_loop("c")
>"cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc"
(128個)
再帰関数
def division
return self * 2
end
def cell_divison(cell)
return cell if cell.length > 100
cell = cell.divison.cell_division
end
p cell_division("c")
>"cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc"
(128個)
解説
以上の例から再帰関数のイメージはつかめるんじゃないでしょうか。
計算時間はほとんど同じです。これは文字列を単純に二倍にするからloop関数のほうが楽に見えるが、直感的には再帰関数の方が理解しやすい場合もあります。
cellが再帰的に分裂をしている様子を理解できます。(再帰的にのイメージを持っていないとわかりづらいが)
再帰関数 VS ループ
再帰関数
メリット
わかりやすくなる可能性がある。
デメリット
メモリー使用量、実行速度(あまり変わらない気がするが)
→ 再帰呼び出しをかけるたびに、新しいスタック領域が必要になるため。
再帰呼び出しし過ぎるとスタックオーバーフローする可能性がある。
対策
引数を値渡しにする。
並行処理で処理速度をあげられる可能性が少しある。
ループ
メリット
メモリを食わない。
デメリット
ネストすると見づらくなる可能性がある。
再帰関数例
- 階乗計算
- フィボナッチ数列
- ハノイの塔
- マージソート
- クイックソート
等。
全て自分自身に同じ法則で処理し続けることで解に収束していく様子を表している。