【Dart】再帰関数って何？

コードを読んでいたら関数の中で自分自身の関数を呼び出しているのを
見つけたんだけど、これってどういう処理なのかな？

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

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

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

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

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

再帰関数とは
まとめ
参考
編集後記（2022/5/27）

再帰関数とは

再帰関数の例

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

例を挙げて解説します。

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

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

  for (int i = 0; i <= n; i++) {
    temp += i;
  }

  return temp;
}

引数の数までを足し合わせて合計を表示する関数iterativeSumの例です。

これを再帰関数を使って書くと、このようになります。

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

int recursiveSum(int n) {
  if (n <= 0) {
    return 0;
  }

  return n + recursiveSum(n - 1);
}

この2つは同じ結果を返します。

後者のほうがコードがスッキリしているように見えますね！

ただ、一体何をしているのかは分かりづらいです。
ステップを追って解説します。

引数が0の時

recursiveSum(0)の結果を考えます。

最初の条件分岐if (n <= 0) でn=0でtrueとなるため、
条件分岐の中に入り、0を返してこの関数の処理は終了となります。

引数が1の時

recursiveSum(1)の結果を考えます。

n=1 > 0のため、最初の条件分岐はスキップします。

  return n + recursiveSum(n - 1);

ですが、n=1のため、1+recursiveSum(0)の結果を返します。

ここでrecursiveSum(0)が実行されます。

最初の条件分岐if (n <= 0) でn=0でtrueとなるため、
条件分岐の中に入り、0を返してこの関数の処理は終了となります。

結果、recursiveSum(1)は、1+0となり、結果の1が返されます。

引数が2の時

recursiveSum(2)の結果を考えます。

n=2 > 0のため、最初の条件分岐はスキップします。

  return n + recursiveSum(n - 1);

ですが、n=2のため、2+recursiveSum(1)の結果を返します。

ここでrecursiveSum(1)が実行されます。

前述の通り、1+recursiveSum(0)の結果を返します。

recursiveSum(0) は0を返すので、結果として、

2 + ( 1 + 0 ) で3が返されます。

引数が5の時

だんだんわかってきたでしょうか？

ちょっと数値を飛ばして、recursiveSum(5)の結果を考えます。

n=5 > 0のため、最初の条件分岐はスキップします。

  return n + recursiveSum(n - 1);

ですが、n=5のため、5+recursiveSum(4)の結果を返します。

ここでrecursiveSum(4)が実行されます。

これは、n=4のため、4+recursiveSum(3)の結果を返します。

ここでrecursiveSum(3)が実行され、3+recursiveSum(2)の結果を返します。

さらに、recursiveSum(2)が実行され、2+recursiveSum(1)の結果を返します。

recursiveSum(1)が実行され、1+recursiveSum(0)の結果を返します。

recursiveSum(0)が実行され、0を返して処理は終了、合計に入ります。

まとめると、

5 + 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

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

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