From: 643-408-1753@kylheku.com   
      
   On 2025-10-22, Rosario19  wrote:   
   > On Tue, 30 Sep 2025 16:12:14 -0000 (UTC), Kaz Kylheku wrote:   
   >   
   >>On 2025-09-30, Janis Papanagnou  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.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)