Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #394666

Re: Optimization of cascading recursions in "C" compilers?

Show all headers | View raw

On 2025-10-22, Rosario19 <Ros@invalid.invalid> wrote:
> On Tue, 30 Sep 2025 16:12:14 -0000 (UTC), Kaz Kylheku wrote:
>
>>On 2025-09-30, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>>> In another newsgroup the question came up to what degree the
>>> GNU "C" compilers can handle optimization of recursions like
>>> fib() or ack(), i.e. cascading ones. Somebody here may know?
>>
>>What exactly are you talking about? The ability to unroll one or more
>>levels of recursion by inlining cases of a function into itself
>>to create a larger functon that makes fewer calls?
>>
>>The common way fib is written recursively doesn't lend to
>>tail call optimization; it has to be refactored for that.
>>
>>The usual way Ackermann is written, it has some tail calls
>>and a non-tail call, since one of its cases returns
>>a call to ack, which has an argument computed by calling ack.
>>
>>> Can we expect that (with the higher optimization levels) the
>>> exponential complexity from cascaded recursion gets linearized?
>>
>>I'm reasonably sure that GCC is not going to recognize and linearize
>>"return fib(n - 1) + fib(n - 2)" recursion. You have to do it yourself
>>with explicit memoization or iterative rewrite.
>
> iterative fibonacci it seems many time faster than the recursive one.
> I don't know if the compiler can optimize until that point...

iterative fibonacci can be expressed by tail recursion, which
the compiler can optimize to iteration.

You have to refactor fib for tail recursion; it may be easier
to start with the iterative version and turn the loop into
a tail call.

Iterative fib(n) starts with the vector v = <0, 1> and then
performs the step n times, returning the second element of
the vector.

The step is to multiply the vector by the matrix

            [ 0 1 ]  
  v_next =  [ 1 1 ]  v

In other words

  v_next[0] =        v[1]
  v_next[1] = v[0] + v[1]

Thus a tail-recursive fib can look like this. The
recursive helper function:

  static int fib_tail(int v0, int v1, int n)
  {
     if (n == 0)
        return v0 + 1;
     else
        return fib_tail(v1, v0 + v1, n - 1);
  }

plus the entry point that conforms to the expected fib API:

  int fib(int n)
  {
     return fib_tail(0, 1, n);
  }

When I compile that with GCC11 for X86-64, using -O3 -S,
I get this [edited for brevity by omitting various environment-related
cruft]:

fib:
        movl    $1, %eax
        xorl    %edx, %edx
        testl   %edi, %edi
        jne     .L2
        jmp     .L8
.L5:
        movl    %ecx, %eax
.L2:
        leal    (%rdx,%rax), %ecx
        movl    %eax, %edx
        subl    $1, %edi
        jne     .L5
        addl    $1, %eax
        ret
.L8:
        ret

The static helper function fib_tail has disappeared, inlined into fib, and
turned from recursion to iteration.

GCC is not going to turn this:

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

into the above pair of functions, or anything similar.

That's not ordinary optimization of the type which improves the code generated
for the user's algorithm; that's recognizing and redesigning the algorithm.

The line between those is blurred, but not /that/ blurred.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-09-30 17:54 +0200
  Re: Optimization of cascading recursions in "C" compilers? David Brown <david.brown@hesbynett.no> - 2025-09-30 18:04 +0200
    Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 00:15 +0200
  Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-09-30 16:12 +0000
    Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 00:07 +0200
      Re: Optimization of cascading recursions in "C" compilers? Ben Bacarisse <ben@bsb.me.uk> - 2025-10-01 10:05 +0100
        Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 19:01 +0200
          Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 19:08 +0200
            Re: Optimization of cascading recursions in "C" compilers? Ben Bacarisse <ben@bsb.me.uk> - 2025-10-02 00:48 +0100
              Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-02 05:25 +0200
                Re: Optimization of cascading recursions in "C" compilers? Ben Bacarisse <ben@bsb.me.uk> - 2025-10-03 15:09 +0100
                Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-03 16:47 +0200
    Re: Optimization of cascading recursions in "C" compilers? bart <bc@freeuk.com> - 2025-10-01 00:02 +0100
      Re: Optimization of cascading recursions in "C" compilers? antispam@fricas.org (Waldek Hebisch) - 2025-10-01 01:22 +0000
    Re: Optimization of cascading recursions in "C" compilers? Rosario19 <Ros@invalid.invalid> - 2025-10-23 00:37 +0200
      Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-22 23:36 +0000
        Re: Optimization of cascading recursions in "C" compilers? Rosario19 <Ros@invalid.invalid> - 2025-10-24 09:53 +0200
          Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-24 15:36 +0200
            Re: Optimization of cascading recursions in "C" compilers? Michael S <already5chosen@yahoo.com> - 2025-10-24 17:35 +0300
              Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-24 17:22 +0200
                Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-24 17:14 +0000
                Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-24 20:31 +0200
                Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-24 23:59 +0000
                Re: Optimization of cascading recursions in "C" compilers? James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-10-27 05:48 -0400
                Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-27 12:52 +0100
                Re: Optimization of cascading recursions in "C" compilers? James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-10-27 14:41 -0400
                Re: Optimization of cascading recursions in "C" compilers? Michael S <already5chosen@yahoo.com> - 2025-10-27 22:33 +0200
                Re: Optimization of cascading recursions in "C" compilers? James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-10-27 16:52 -0400
                Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-27 21:03 +0000
                Re: Optimization of cascading recursions in "C" compilers? antispam@fricas.org (Waldek Hebisch) - 2025-10-28 01:58 +0000

csiph-web