Recursive factorial in C++ and Scala

recursive-factorial.md

It turns out that both GCC and Clang compile recursive code for factorial as a simple loop:

template<typename T>
constexpr
T factorial_impl(T value) {
    return value <= 1 ? 1 : value * factorial(value - 1);
}

long factorial(long arg) { return factorial_impl(arg); }

__int128 factorial(__int128 arg) { return factorial_impl(arg); }

GCC will compile both functions using a loop, even from very ancient versions, as can be seen using the compiler explorer.

Clang would not optimize the tail recursion even if we would write this:

__int128 factorial(unsigned arg, __int128 soFar) {
    if(arg <= 1) { return soFar; }
    return factorial(arg - 1, arg * soFar);
}

Which eliminates the trail multiplication, but still clang would not eliminate the trail recursion. Disappointment aside, the equivalent code in Scala would suffer tail recursion, because they chose to base it off the Java Virtual Machine which sucks balls.

Their programmers have to recurr to trampolines, which is not what we normally understand as trampolines but in reality are like a fixed point operator, a thing that takes a thunk, a callable, and repeatedly loops calling the callable until the callable returns a done state. This is explained in this blog.

I saw code for the factorial using trampolines here:

sealed trait Bounce[A]
case class Done[A](result: A) extends Bounce[A]
case class Call[A](thunk: () => Bounce[A]) extends Bounce[A]

def trampoline[A](bounce: Bounce[A]): A = bounce match {
  case Call(thunk) => trampoline(thunk())
  case Done(x) => x
}

def factorial(n: Int, sum: BigInt): Bounce[BigInt] {
	if (n <= 2) Done(sum)
	else Call(() => Factorial(n - 1, n * sum))
}

object Factorial extends Application {
	println(trampoline(factorial(100000, 1)))
}

This kind of busy work is what I hate the most in any programming language.