GLSL icon indicating copy to clipboard operation
GLSL copied to clipboard

Supporting tail-recursion in GLSL

Open jarble opened this issue 3 years ago • 1 comments

GLSL currently does not support tail recursion, but this feature could be easily implemented using tail-call optimization. For example, this function is not yet compatible with GLSL:

int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

But it's possible to eliminate recursion here, replacing the recursive call with a for-loop:

int fib(int n)
{
  int a = 0, b = 1, c, i;
  if (n == 0)
    return a;
  for (i = 2; i <= n; i++)
  {
     c = a + b;
     a = b;
     b = c;
  }
  return b;
}

Are there any plans to implement tail-recursion in a future version of GLSL?

jarble avatar Sep 04 '20 18:09 jarble

We tend to not want to have semantics expressed in terms of what an optimizer might be able to do. Maybe that can be done for tail recursion, but it needs a name and specification that pins down exactly which cases must work and which cases must be rejected, without any implication of how smart an optimizer might be.

johnkslang avatar Sep 07 '20 05:09 johnkslang