From: Ros@invalid.invalid
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...
#include
unsigned fib(unsigned n){if(n<2)return n; return fib(n-1)+fib(n-2);}
unsigned f(unsigned n)
{unsigned r,i,j;
if(n==0) return 0;
n-=1;
for(r=j=i=1;n;--n)
{r=j;j+=i;i=r;}
return r;
}
main(void)
{unsigned i, r;
for(i=0;i<40;++i)
{r=fib(i);
printf("fibonacciRic(%u)=%u\n", i, r);
}
for(i=0;i<40;++i)
{r=f(i);
printf("fibonacciIter(%u)=%u\n", i, r);
}
return 0;
}
---------------
fibonacciRic(0)=0
fibonacciRic(1)=1
fibonacciRic(2)=1
fibonacciRic(3)=2
fibonacciRic(4)=3
fibonacciRic(5)=5
fibonacciRic(6)=8
fibonacciRic(7)=13
fibonacciRic(8)=21
fibonacciRic(9)=34
fibonacciRic(10)=55
fibonacciRic(11)=89
fibonacciRic(12)=144
fibonacciRic(13)=233
fibonacciRic(14)=377
fibonacciRic(15)=610
fibonacciRic(16)=987
fibonacciRic(17)=1597
fibonacciRic(18)=2584
fibonacciRic(19)=4181
fibonacciRic(20)=6765
fibonacciRic(21)=10946
fibonacciRic(22)=17711
fibonacciRic(23)=28657
fibonacciRic(24)=46368
fibonacciRic(25)=75025
fibonacciRic(26)=121393
fibonacciRic(27)=196418
fibonacciRic(28)=317811
fibonacciRic(29)=514229
fibonacciRic(30)=832040
fibonacciRic(31)=1346269
fibonacciRic(32)=2178309
fibonacciRic(33)=3524578
fibonacciRic(34)=5702887
fibonacciRic(35)=9227465
fibonacciRic(36)=14930352
fibonacciRic(37)=24157817
fibonacciRic(38)=39088169
fibonacciRic(39)=63245986
fibonacciIter(0)=0
fibonacciIter(1)=1
fibonacciIter(2)=1
fibonacciIter(3)=2
fibonacciIter(4)=3
fibonacciIter(5)=5
fibonacciIter(6)=8
fibonacciIter(7)=13
fibonacciIter(8)=21
fibonacciIter(9)=34
fibonacciIter(10)=55
fibonacciIter(11)=89
fibonacciIter(12)=144
fibonacciIter(13)=233
fibonacciIter(14)=377
fibonacciIter(15)=610
fibonacciIter(16)=987
fibonacciIter(17)=1597
fibonacciIter(18)=2584
fibonacciIter(19)=4181
fibonacciIter(20)=6765
fibonacciIter(21)=10946
fibonacciIter(22)=17711
fibonacciIter(23)=28657
fibonacciIter(24)=46368
fibonacciIter(25)=75025
fibonacciIter(26)=121393
fibonacciIter(27)=196418
fibonacciIter(28)=317811
fibonacciIter(29)=514229
fibonacciIter(30)=832040
fibonacciIter(31)=1346269
fibonacciIter(32)=2178309
fibonacciIter(33)=3524578
fibonacciIter(34)=5702887
fibonacciIter(35)=9227465
fibonacciIter(36)=14930352
fibonacciIter(37)=24157817
fibonacciIter(38)=39088169
fibonacciIter(39)=63245986
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
