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

Groups > comp.lang.c > #157930

Re: Recursion v Memoization

Show all headers | View raw

Real Troll <real.Troll@trolls.com> writes:

> We sometimes resort to using simple methods such as Recursion
> functions or interactive functions but Memoization method can be
> very useful.  For example to generate 45 Fibonacci numbers using
> recursion I used this function:
>
> int fibonacci(int input)
> {
>  if (input == 0 || input == 1)
>  {
>  return input;
>  }
>  else
>  {
>  return fibonacci(input - 1) + fibonacci(input - 2);
>  }
> }
>
> but using an array to store the numbers and to reuse the previous
> calculated values can save a lot of time.  [...]

Better simply to use a non-exponential algorithm:

/*** cut here ***/
#include <stdio.h>

typedef unsigned long long ULL;

static  ULL  fibonacci( unsigned );
static  ULL  ff2( ULL, ULL, unsigned, unsigned );

int
main( int argc, char *argv[] ){
    unsigned n;
    for(  n = 0;  n < 94;  n++  ){
        ULL fn = fibonacci( n );
        if(  argc > 1  )  printf( " fib( %2u ) is %25llu\n", n, fn );
    }
    return  0;
}

ULL
fibonacci( unsigned n ){
    unsigned high_bit = -1U ^ -1U>>1;
    return  ff2( 1, 0, high_bit, n );
}

ULL
ff2( ULL a, ULL b, unsigned m, unsigned n ){
    return  m == 0  ?  b
        :   m & n   ?  ff2( 2*a*b + b*b, a*a + 2*a*b + 2*b*b, m>>1, n )
        :   ff2( a*a + b*b, 2*a*b + b*b,                      m>>1, n );
}

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

Thread

Recursion v Memoization Real Troll <real.Troll@trolls.com> - 2020-12-29 16:30 -0500
  Re: Recursion v Memoization Bart <bc@freeuk.com> - 2020-12-29 22:17 +0000
    Re: Recursion v Memoization Ike Naar <ike@sdf.org> - 2020-12-30 05:47 +0000
      Re: Recursion v Memoization Bart <bc@freeuk.com> - 2020-12-30 11:55 +0000
  Re: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-29 21:51 -0800
  Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-31 00:46 -0800
    Re: Recursion v Memoization David Brown <david.brown@hesbynett.no> - 2020-12-31 16:12 +0100
      [OT] was: Recursion v Memoization Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-01-01 15:59 +0000
        Re: [OT] was: Recursion v Memoization David Brown <david.brown@hesbynett.no> - 2021-01-01 17:35 +0100
        Re: [OT] was: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-01 08:40 -0800
        Re: [OT] was: Recursion v Memoization Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-01-02 10:36 -0800
          Re: [OT] was: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-01-02 16:59 -0800
          Re: [OT] was: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-01-02 17:00 -0800
    Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-02 18:56 -0700
      Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-04 19:56 -0800
        Re: Recursion v Memoization beej@beej.us (Beej) - 2021-01-05 04:27 +0000
          Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-07 04:54 -0800
            Re: Recursion v Memoization beej@beej.us (Beej) - 2021-01-11 05:43 +0000
              Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-11 06:34 -0800
        Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-05 14:35 -0700
          Re: Recursion v Memoization Real Troll <real.troll@trolls.com> - 2021-01-05 16:45 -0500
            Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-05 15:33 -0700
          Re: Recursion v Memoization Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-01-06 09:40 +0000
            Re: Recursion v Memoization Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-01-06 17:09 +0000
          Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-07 06:37 -0800
  Re: Recursion v Memoization Andrey Tarasevich <andreytarasevich@hotmail.com> - 2020-12-31 02:33 -0800

csiph-web