再帰とコールスタックについて。

再帰関数について


再帰関数は、まあ説明するまでもないが自分自身を呼び出す関数のこと。
よくあるのは階乗を求めるやつとか。階乗を求める式は…

$n! = n × (n - 1) × (n - 2) × (n - 3) … × 1$

となる。これをプログラムで書くと下記のようになる。今回はScalaで書いた。

1
2
3
4
5
6
7
8
9
println(f(3))

def f(x: Int): Int = {
if (x == 1) {
x
} else {
x * f(x - 1)
}
}

上記は3の階乗を求めている。

コールスタック


関数が実行された際に、引数とかローカル変数とか戻り値とか戻り先とかその辺の情報をスタック領域に保持していく。これをコールスタックという。後入れ先出(LIFO)である。

先ほどの3の階乗を求めるプログラムのコールスタックを超絶雑な図で書くと下記のようなイメージになる。

スタックオーバーフロー


コールスタックは当然スタック領域を消費するが、これが積み重なりすぎると発生するのがスタックオーバーフロー。例えば前述の階乗を求めるプログラムで30000ぐらいの階乗を求めようとすると発生する。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
println(f(30000))

def f(x: Int): Int = {
if (x == 1) {
x
} else {
x * f(x - 1)
}
}

/*
Exception in thread "main" java.lang.StackOverflowError
at recursion.Basic$.f(Basic.scala:11)
at recursion.Basic$.f(Basic.scala:11)
at recursion.Basic$.f(Basic.scala:11)
*/

スタックオーバーフローを回避するには2つの方法がある。

  • ループに書き換える
  • 末尾再帰をつかう

今回は続けて末尾再帰について書く。

末尾再帰


末尾再帰とは…

  • 自分自身の呼び出しを行っているケース
  • 計算結果を渡す

階乗を例にすると通常の再帰が自身を呼び出す際に $n × (n - 1)$ を行っているのに対して計算結果をそのまま渡す。具体的にコードで書くと下記のようになる。

1
2
3
4
5
6
7
8
9
println(f(30000))

def f(x: Int, acc: Int = 1): Int = {
if (x == 1) {
acc
} else {
f(x - 1, x * acc)
}
}

一般的にaccumurator(蓄積者)を略してaccとかそういう変数名にすることが多いようだ。こうすると、常に計算結果を次の関数に渡すことになる。のでコールスタックを消費しない。ただし言語による。

末尾再帰最適化


末尾再帰最適化とは、末尾再帰を書くとコンパイラが最適化してくれることをいう。つまり末尾再帰を書いても言語として最適化されるかどうかは別ということになる。

どの言語で最適化されるのかは詳しく調べていないけれども、Scalaでは最適化される。

参考


下記の記事を参考にさせていただきました。ありがとうございました。

再帰関数の末尾再帰(最適化)について