Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #394429
| From | Ben Bacarisse <ben@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Optimization of cascading recursions in "C" compilers? |
| Date | 2025-10-01 10:05 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87ikgzm1pi.fsf@bsb.me.uk> (permalink) |
| References | <10bgug3$3pmee$1@dont-email.me> <20250930090324.208@kylheku.com> <10bhkbk$3vleo$1@dont-email.me> |
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
> On 30.09.2025 18:12, 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?
>
> No. (see below)
>
>> 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.
>
> To (hopefully) answer your question above and clear up what I
> meant (and what I haven't meant)...
>
> I'm not speaking about transformations of recursive calls to
> iterative loops (which doesn't reduce algorithmic complexity).
> I was rather thinking about transformations like the following
> (where fib-1 is the standard form, that you show above as fib)
>
> fib-1:
> func __(_){return(_>2?__(--_)+__(--_):1)}
>
> fib-2:
> func ___(_) { return __(_,x^x,x^x^x) }
> func __(_,_x,x_) { return --_?__(_,x_,_x+x_):_x+x_ }
>
> I apologize for the obfuscated format (it's code I've written
> for a fun post in comp.lang.awk), but we can still see the
> call structure (I hope). Both forms obey the functional form.
Particularly hard since some newsreaders interpret _text_ as
underlining. Mine did. Took me a while to see that this was AWK code
at all! Since this is comp.lang.c, let's have it in C (without the
decrement operations):
typedef unsigned int N;
N fib1(N n) { return n > 2 ? fib1(n-1) + fib1(n-2) : 1; }
N fib_aux(N n, N a, N b) { return n > 1 ? fib_aux(n-1, b, a+b) : a+b; }
N fib2(N n) { return fib_aux(n, 1, 0); }
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv)
{
printf("%u\n", fib2(argc > 1 ? atoi(argv[1]) : 40));
}
> The second, a formally refactored form of the first doesn't
> have those (time consuming) *cascaded* calls any more.
To me, "formally refactored" means there would be a set of formal rules
that can be applied. What rules did you have in mind?
As for your general point, it can't be done in general or we'd most
likely know that P = NP. On the specific point about ack(), Ackermann
devised the function to show that not all total recursive functions are
primitive recursive.
--
Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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