Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #394707
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Optimization of cascading recursions in "C" compilers? |
| Date | 2025-10-24 17:35 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20251024173549.00002111@yahoo.com> (permalink) |
| References | (1 earlier) <20250930090324.208@kylheku.com> <psmifklj51ebbbjhqrglpq96fkpikrlpq9@4ax.com> <20251022161629.185@kylheku.com> <d5bmfktijpt62hvbdo4irgs0as8b17v3qg@4ax.com> <10dfvds$2k51h$1@dont-email.me> |
On Fri, 24 Oct 2025 15:36:58 +0200
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> On 24.10.2025 09:53, Rosario19 wrote:
> >
> >
> >> 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.
> >
> > int fib1(int n){return fib_tail(0, 1, n);}
> >
> > is different from
> >
> > int fib(int n){if(n<2) return 1;return fib(n - 1) + fib(n - 2);
> >
> >
> > both these function calculate from the 0 1 the number result, but
> > fib() start to calculate from n goes dowwn until n=0, than goes up
> > until n=input, instead fib1() go only down for n. It seen the calls
> > (fib has 2 call each call... instead fib_tail() just 1), I think
> > fib() is O(n^2) instead fib1 is O(n).
>
> It's worse; it's O(2^N).
>
> Janis
>
Actually, the number of calls in naive recursive variant = 2*FIB(N)-1.
So, O(1.618**n) - a little less bad than your suggestion.
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