Scalaで再帰関数を使う際に覚えておくと役に立つこと

#はじめに
###お命頂だい！！！
はじめまして、リクームです。
ギ◯ュー特戦隊を辞めて、最近scalaの勉強をはじめました。
自分が勉強していて気になったことや、参考になったことを記事に残していこうと思います。

間違っていることなどありましたらご指摘ください！！
##再帰関数
関数を使った技法の代表的なものに再帰関数というものがあります。
具体的にどんなものかというと、"関数の中で関数自身を呼び出す"といった処理を行う技法です。
よく例題などで挙げられるのは「１からnまでの数字を足し合わせる」といった繰り返し処理を行うものです。
実際にプログラミングで実現すると以下のようになります。

sum

//1 から n までの和を求める
def sum(n: Int): Int = {
    if (n == 0) {
      return 0
    }
    sum(n - 1) + n
  }

簡単に説明すると、sumという関数の中でもう一度sum関数を呼び出しています。
再度実行する際は、nから1を引いた値とn足し合わせて、nから1を引いた値をsum関数の引数に渡して再度sumを実行します。
引数が0になったタイミングでreturnして処理を終了します。

上記のような処理を行うことができる再帰関数ですが、気をつけなければいけない点があります。
##StackOverflowError
再帰関数は、メソッドの呼び出しの時に利用されるコールスタックと呼ばれる領域を使い果たしてしまうと、StackOverflowErrorが発生します。
※コールスタックとは、メソッドの呼び出しの際にその上位の階層の情報（関数の戻り先アドレスや、引数、ローカル変数）を保存しておく領域のことを指します。

実際にStackOverflowErrorを発生させてみましょう。

sum実行

  //10万という大きな数字を引数に渡す
  sum(100000)

sum関数に対して「100000」という大きな値を引数に渡して実行してみます。
すると、、、

sum(100000)実行結果

scala> Main
//StackOverflowErrorが発生
java.lang.StackOverflowError
  at Main$.sum(Main.scala:9)

StackOverflowErrorが発生しましたね。
このように、再帰を繰り返し行ってコールスタック領域を使い果たしてしまうとStackOverflowError発生するということが体現できたかと思います。
このように大きな値を足し合わせることを、再帰関数で実現することは不可能なのでしょうか？？？
実は、、、実現できちゃうんです！！
scalaには末尾再帰最適化という機能が用意されており、StackOverflowError防ぐことができます！
##末尾再帰最適化
末尾再帰最適化は、再帰関数の呼び出しが必ず関数の末尾に来るような記述としておくことで、コンパイル時に内部的にループ処理に置き換えてくれます。
先ほどのsum関数を少し書き換えてみましょう。

sum

  //結果を足しあわせておくための引数accを追加
  def sum(n: Int, acc: Int): Int = {
    if (n == 0) {
      //nが0になったら足し合わせた結果を返す
      acc
    } else {
      //結果を足し合わせて引数に渡す👈重要！
      sum(n - 1, acc + n)
    }
    //結果を出力
    println(sum(100000, 0))
  }

足し合わせた結果を保持しておき、次の呼び出し時に再度accを渡すようにしました。
先ほどは「100000」を引数に渡した場合はエラーになってしまいましたが、今回は、、

scala> Main
705082704

わーお！ちゃんと結果が表示されました！
returnしている箇所に注目して欲しいのですが、再帰関数の呼び出しだけを行なっています。
scalaではこのような書き方にすることでコンパイル時に内部でループ処理に置き換えてくれるのです。

ほんとに〜？？？

実際に逆コンパイルして見てみましょう！

// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3)
// Source File Name:   Main.scala

import scala.Predef$;
import scala.runtime.BoxesRunTime;

public final class Main$
{

    public int sum(int n, int acc)
    {
        //whileに置き換わっている！！😆
        while(n != 0)
        {
            acc += n;
            n = n - 1;
        }
        return acc;
    }

    private Main$()
    {
        MODULE$ = this;
        Predef$.MODULE$.println(BoxesRunTime.boxToInteger(sum(0xf4240, 0)));
    }

    public static Main$ MODULE$;

    static
    {
        new Main$();
    }
}

こんな感じで内部的にループ処理に置き換えてくれることが実際にわかりました。

##tailrecアノテーション
実はscalaには再帰関数を使う上で、とても役に立つ機能があります。
それが「tailrecアノテーション」というものなのですが、このアノテーションを用いることで末尾再帰最適化がかからない再帰関数に対して、コンパイルエラーを発生させることができます。

###めちゃ便利！！！！

実際に使ってみましょう。

sum

  //末尾再帰最適化がされていない再帰関数
  @tailrec
  def sum(n: Int): Int = {
    if (n == 0) {
      return 0
    }
    sum(n - 1) + n
  }

tailrecアノテーションを用いることによって以下のコンパイルエラーが発生します。

Error:(19, 16) could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
    sum(n - 1) + n

お〜、見事に怒られましたね。
こんな感じでコンパイル時にエラーにしてくれるのは、ほんとにありがたいですね！
ぜひ活用していきましょー！！

#まとめ

• StackOverflowErrorを回避する策として末尾再帰最適化というものがある。
• tailrecアノテーションの用いることで末尾再帰最適化されていない再帰関数の場合は、コンパイルエラーを発生させることができる。