【Dart】再帰関数って何？

コードを読んでいたら関数の中で自分自身の関数を呼び出しているのを

見つけたんだけど、これってどういう処理なのかな？

難しくてよくわからないわ！

本記事ではそんな疑問にお答えします。

自分自身を呼び出し、処理を再帰的に行う関数、再帰関数についてDartでの例を交えて解説します。

本記事の目的は再帰関数を使ったコードを読めるようになることです。実際に使えるようになるのはなかなか難しいですが、使ったコードにぶつかった時に慌てなくて済むように、基礎をしっかりおさえておきましょう！

ぜひ読んでみてください！

再帰関数とは

再帰関数の例

再帰関数とは、関数の中で自分自身を呼び出し、処理を行う関数のことです。

例を挙げて解説します。

void main() {
  print(iterativeSum(10));
}

int iterativeSum(int n) {
  int temp = 0;

  for (int i = 0; i recursiveSum(4)
=> 5 + ( 4 + recursiveSum(3) )
=> 5 + ( 4 + ( 3 +recursiveSum(2) ) )
=> 5 + ( 4 + ( 3 +  ( 2 + recursiveSum(1) ) ) )
=> 5 + ( 4 + ( 3 +  ( 2 + ( 1 + recursiveSum(0) ) ) ) )
=> 5 + ( 4 + ( 3 +  ( 2 + ( 1 + 0 ) ) ) )
=> 15

といった形で計算され、15が答えとして返ります。

このコードが引数以下の数字の合計を返すこと、がわかったかと思います。

再帰関数の良い点

良い点は、再帰関数で書くとコードをよりスッキリと、端的に書くことができることです。

上での例示のとおり、コードを短く書くことができます。

再帰関数の弱点

弱点は3つあります。

１つ目は、コードを理解するのにちょっとコツが要ることです。特に初心者の方がこの再帰関数を理解しようとすると、手こずるかと思いますコードを読む側には優しくないコードとなってしまうのが、１つ目の弱点です。

２つ目は、forで行った時に比べ、パフォーマンスが良くないことです。以下のDartPadでforループで行う場合と、再帰的に行う場合の実行時間を比較しています。

DartPad

An online Dart editor with support for console and Flutter apps.

dartpad.dev

何回か実行してみると、再帰的に行う場合の方が時間がかかることがわかると思います。このように、パフォーマンスが悪くなってしまうことが弱点の２つ目です。

3つ目はメモリを消費することです。上のDartPadにてn=10000を計算すると、 Uncaught RangeError: Maximum call stack size exceededError: RangeError: Maximum call stack size exceeded とスタックオーバーフローのエラーが出ます。計算途中で、5+recursiveSum(4)の5の部分をメモリで記録しておかなければいけないため、メモリを消費してしまうからです。メモリ消費でのエラーが発生し得ること、これが3つ目の弱点です。