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

Groups > comp.lang.c > #158079

[OT] was: Recursion v Memoization

Show all headers | View raw

David Brown <david.brown@hesbynett.no> writes:

> On 31/12/2020 09:46, Tim Rentsch wrote:
>> 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:
>> 
>
> "Better" depends on what you are trying to do.  For demonstrating the
> benefits of memoization on recursive functions, the OP's algorithm is
> better than yours.  For actually calculating Fibonacci numbers
> efficiently, a simple "powers of phi" algorithm is better than yours.

Is it?  Without "big nums" you might as well just have a table and with
large numbers I'm not sure how you control the errors.  What did you
have in mind?

> For demonstrating how the apparently exponentially recursive Fibonacci
> algorithm can be turned into an efficient recursive algorithm, yours is
> a nice choice (but it needs a good tutorial on how it works in order to
> be useful).

In Haskell you can give a recursive definition that gives you the
memoization "for free", so to speak:

  fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)

  main = mapM print $ take 50 fibonacci

(The : operator is "cons" -- list building.  zipWith makes one list from
two by applying the give function to the elements pairwise.)

-- 
Ben.

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