末尾最適化メモ

tailrec fun a(i: Int) {
  if (cond) return base
  return calc(i, a(newParam(i)))
}

以上のような一般化された1引数の末尾再帰関数を考える。base = 0, calc = $1 + $2, newParam(i) = i - 1, cond = i > 0 と読み替えると (0..i).sum() になる。 ここで、末尾再帰はループに展開できるのでループに展開する。

fun a(i: Int) {
  var iCopy = i // parameter i is val
  var res = base
  while (!cond) {
    res = calc(res, iCopy)
    iCopy = newParam(iCopy)
  }
  return res
}

base = 0, calc = $1 + $2, newParam(i) = i - 1, cond = i > 0 で考えてみる Calling a(6):

res	iCopy	iCopy >= 0
-	6	-
0	6	T
6	5	T
11	4	T
15	3	T
18	2	T
20	1	T
21	0	F

よし。ちゃんと21で合っている。 任意個の引数の関数をtailrecする場合でも

res = calc(res, p1, p2, p3, /* ... */, pN)
p1 = newParam1(p1)
p2 = newParam2(p2)
p3 = newParam3(p3)
// ...
pN = newParamN(pN)

として同様に適用できる。

備考: kotlincはおそらく分岐予測のペナルティを減らすために

while(true) {
  if (cond) return acc;
}

としている。