【Dart】 再帰関数 って何?

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

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

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

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

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

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

再帰関数 とは

再帰関数 の例

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

例を挙げて解説します。

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=0trueとなるため、
条件分岐の中に入り、0を返してこの関数の処理は終了となります。

引数が1の時

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

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

  return n + recursiveSum(n - 1);

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

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

最初の条件分岐if (n <= 0)n=0trueとなるため、
条件分岐の中に入り、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つあります。

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

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

404 Page not found

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

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

まとめ

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

いかがだったでしょうか?

再帰関数について理解が深まりましたか?

弱点の方が多く解説したため、使わないほうが良いのでは?と思われるかも知れません。
ですが、使い所と使い方を選べば、強力な効果を発揮するのが再帰関数です。

再帰関数の使い所等々については、以下の記事がとても勉強になるかと思います。
興味のある方はぜひ読んでみてください。

再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに再帰関数は初めて学ぶときに壁になりがちでなんとなくわかった...けれどどんな場面で使えるのだろう...いい感じの例を探したい!という気持ちになりがちです。再帰関数は、なかなかそ…

本記事があなたのアプリ開発の一助となれば幸いです。

Flutterを一緒に学んでみませんか?
Flutter エンジニアに特化した学習コミュニティ、Flutter大学への入会は、
以下の画像リンクから。



参考

Higher-Order Functions & Recursion in Dart [Functional Programming — Part 5]
Go the Declarative way!

編集後記(2022/5/27)

今回は再帰関数についての記事でした。

ちょっとマニアックなテクニックについての記事だったかと思います。
ただ引き出しを大きくするのは大事だと思っています。

いつか、必要となった時につかえるように、頭の片隅に記憶しておくと良いかと思います。

こういうテクニックは競技プログラミング等でよく使うイメージがあります。
Dartの競技プログラミングがあったら面白そうだな、とふと思いました。
(Flutter Puzzle Hack のようなハッカソンはありましたが。)

Flutter/Dartが広まっていけば、いつかできるかもしれませんね。

将来に期待です。

週刊Flutter大学では、Flutterに関する技術記事、Flutter大学についての紹介記事を投稿していきます。
記事の更新情報はFlutter大学Twitterにて告知します。
ぜひぜひフォローをお願いいたします。

タイトルとURLをコピーしました