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

Groups > comp.lang.c > #157872 > unrolled thread

Recursion v Memoization

Back to article view | Back to comp.lang.c

Contents

  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

Page 1 of 2  [1] 2  Next page →

#157872 — Recursion v Memoization

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.   Try this example:

#include <stdio.h>

int main()
{
     int Fib[45];
     Fib[0] = 0;
     Fib[1] = 1;
     Fib[2] = 1;

     for (int p = 3; p <= 46; p++)
     {
         Fib[p] = Fib[p - 1] + Fib[p - 2];
     }

     for (int k = 0; k <= 46; k++)
     {
         printf("%d\n", Fib[k]);
     }
}

If you try to calculate the same 45 numbers using recursion will take 
some time to process.  Try it.

Of course using vectors in c++ makes this easier  because you can have 
dynamic size of the list of numbers.  With arrays the size is fixed 
unless you use more code to manage memory allocation.

[toc] | [next] | [standalone]

#157874

On 29/12/2020 21:30, Real Troll wrote:
 > 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.   Try this example:
 >
 > #include <stdio.h>
 >
 > int main()
 > {
 >      int Fib[45];
 >      Fib[0] = 0;
 >      Fib[1] = 1;
 >      Fib[2] = 1;
 >
 >      for (int p = 3; p <= 46; p++)
 >      {
 >          Fib[p] = Fib[p - 1] + Fib[p - 2];
 >      }
 >
 >      for (int k = 0; k <= 46; k++)
 >      {
 >          printf("%d\n", Fib[k]);
 >      }
 > }
 >
 > If you try to calculate the same 45 numbers using recursion will take
 > some time to process.  Try it.
 >
 > Of course using vectors in c++ makes this easier  because you can have
 > dynamic size of the list of numbers.  With arrays the size is fixed
 > unless you use more code to manage memory allocation.

I don't think your example demonstrates memoisation, which should be 
built-in to the function, and not require explicit initialisation.

This example shows how it might work for Fibonacci numbers up to 100, 
even using inefficient recursion:

  int fibonacci(int input)
  {   enum {memlen=100};
      static int memdata[memlen];

      if (input<memlen && memdata[input])
          return memdata[input];

      if (input == 0 || input == 1)
       {
           memdata[input] = input;
           return input;
       }
       else
       {
           memdata[input] = fibonacci(input - 1) + fibonacci(input - 2);
           return memdata[input];
       }
  }

Now it can be speeded up transparently. Fibonacci(46) is now instant, 
instead of taking 17 seconds.

However, recursive Fibonacci is not normally used just to calculate 
Fibonacci numbers; it is a well known benchmark for extreme recursion.

Calling Fibonacci(46) using your version (they vary) should involve 
1,647,462,849 calls. With memoisation enabled, there are only 91 calls, 
which would give highly misleading results.

[toc] | [prev] | [next] | [standalone]

#157883

On 2020-12-29, Bart <bc@freeuk.com> wrote:
> This example shows how it might work for Fibonacci numbers up to 100, 
> even using inefficient recursion:
>
>   int fibonacci(int input)
>   {   enum {memlen=100};
>       static int memdata[memlen];
>
>       if (input<memlen && memdata[input])
>           return memdata[input];
>
>       if (input == 0 || input == 1)
>        {
>            memdata[input] = input;
>            return input;
>        }
>        else
>        {

Here's a bug: at this point, input can be >= memlen; if so, the
assignment to memdata[input] will write outside the array boundary.

>            memdata[input] = fibonacci(input - 1) + fibonacci(input - 2);
>            return memdata[input];
>        }
>   }

[toc] | [prev] | [next] | [standalone]

#157895

On 30/12/2020 05:47, Ike Naar wrote:
 > On 2020-12-29, Bart <bc@freeuk.com> wrote:
 >> This example shows how it might work for Fibonacci numbers up to 100,
 >> even using inefficient recursion:
 >>
 >>    int fibonacci(int input)
 >>    {   enum {memlen=100};
 >>        static int memdata[memlen];
 >>
 >>        if (input<memlen && memdata[input])
 >>            return memdata[input];
 >>
 >>        if (input == 0 || input == 1)
 >>         {
 >>             memdata[input] = input;
 >>             return input;
 >>         }
 >>         else
 >>         {
 >
 > Here's a bug: at this point, input can be >= memlen; if so, the
 > assignment to memdata[input] will write outside the array boundary.


Thanks.

It would really need refactoring with a single point of return to use 
this approach tidily. So it was just a quick demo. (With N=99, I doubt 
the non-memoised version would finish anytime soon.)

[toc] | [prev] | [next] | [standalone]

#157884

On 12/29/2020 1:30 PM, Real Troll wrote:
> 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.   Try this example:
> 
> #include <stdio.h>
> 
> int main()
> {
>      int Fib[45];
>      Fib[0] = 0;
>      Fib[1] = 1;
>      Fib[2] = 1;
> 
>      for (int p = 3; p <= 46; p++)
>      {
>          Fib[p] = Fib[p - 1] + Fib[p - 2];
>      }
> 
>      for (int k = 0; k <= 46; k++)
>      {
>          printf("%d\n", Fib[k]);
>      }
> }
> 
> If you try to calculate the same 45 numbers using recursion will take 
> some time to process.  Try it.

A mixture of the iterative form of a recursion, with actual recursion 
when the buffers are exhausted?

> 
> Of course using vectors in c++ makes this easier  because you can have 
> dynamic size of the list of numbers.  With arrays the size is fixed 
> unless you use more code to manage memory allocation.
> 
> 
> 

[toc] | [prev] | [next] | [standalone]

#157930

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 );
}

[toc] | [prev] | [next] | [standalone]

#157946

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.
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).

[toc] | [prev] | [next] | [standalone]

#158079 — [OT] was: Recursion v Memoization

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.

[toc] | [prev] | [next] | [standalone]

#158084 — Re: [OT] was: Recursion v Memoization

On 01/01/2021 16:59, Ben Bacarisse wrote:
> 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?

The direct calculation of fib(n) is the nearest integer to

	\frac{\phi ^ n}{\sqrt{5}}

For large n, that will be quick to calculate - /if/ you are happy with
the digits you get with floating point on whatever platform you are
using to calculate it.

If you need exact integers for even larger values, then this method is
probably no longer the "best".  You may be better off using :

	fib(2n - 1) = fib(n)^2 + fib(n-1)^2
	fib(2n) = (2.fib(n-1) + fib(n)).fib(n)

or some of the many other identities and methods, including Tim's.  My
point was merely that Tim's suggestion can't be called "better" without
specifying the requirements or preferences for the algorithm, and it
certainly was not "better" for what the OP wanted to show.

> 
>> 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.)
> 

Haskell is certainly a neat language for this kind of thing.  (My
Haskell knowledge is good enough to read such code, but not to write it
without a good bit of trial and error.)

[toc] | [prev] | [next] | [standalone]

#158085 — Re: [OT] was: Recursion v Memoization

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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?  [...]

No, it isn't.  As usual David Brown is talking about things that
he understands less well than he thinks he does, and without
bothering to investigate his assertions.  The algorithm that he
removed, using ff2(), produces more accurate results and also
runs more quickly than a powers of phi algorithm.  I've run the
benchmarks.  (Disclosure:  the algorithm shown in my recent
posting marches through more high order bits than it needs to in
calling the ff2() function.  The version measured does a better
job of choosing bit value to start the iteration, but the ff2()
function is exactly the same.  In any case the measurement
includes both the call to ff2() and the high bit setup before
ff2() is called.)

[toc] | [prev] | [next] | [standalone]

#158101 — Re: [OT] was: Recursion v Memoization

On Friday, 1 January 2021 at 16:00:21 UTC, Ben Bacarisse wrote:
> David Brown <david...@hesbynett.no> writes: 
> 
> > On 31/12/2020 09:46, Tim Rentsch wrote: 
> >> Real Troll <real....@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?
>
I've never used Fibonnaci numbers in a "real" program, by which I mean
one not designed to show off the properties of Fibonnaci numbers themselves.
 
So it's hard to say what a better function would look like. 

[toc] | [prev] | [next] | [standalone]

#158113 — Re: [OT] was: Recursion v Memoization

On 1/2/2021 10:36 AM, Malcolm McLean wrote:
> On Friday, 1 January 2021 at 16:00:21 UTC, Ben Bacarisse wrote:
>> David Brown <david...@hesbynett.no> writes:
>>
>>> On 31/12/2020 09:46, Tim Rentsch wrote:
>>>> Real Troll <real....@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?
>>
> I've never used Fibonnaci numbers in a "real" program, by which I mean
> one not designed to show off the properties of Fibonnaci numbers themselves.

Fwiw, a fun thing to do with them, is to create music. ;^)

https://oeis.org/play?seq=A000045


>   
> So it's hard to say what a better function would look like.
> 

[toc] | [prev] | [next] | [standalone]

#158114 — Re: [OT] was: Recursion v Memoization

On 1/2/2021 10:36 AM, Malcolm McLean wrote:
> On Friday, 1 January 2021 at 16:00:21 UTC, Ben Bacarisse wrote:
>> David Brown <david...@hesbynett.no> writes:
>>
>>> On 31/12/2020 09:46, Tim Rentsch wrote:
>>>> Real Troll <real....@trolls.com> writes:
[...]
> I've never used Fibonnaci numbers in a "real" program, by which I mean
> one not designed to show off the properties of Fibonnaci numbers themselves.

Fwiw, here is some music I plotted on a von Koch curve. It has an odd sound:

https://youtu.be/fvqf029qgEk

[toc] | [prev] | [next] | [standalone]

#158116

Recursive Fibonacci is actually a great function to go through in a
beginning programming class, because you can use it to show

(1) how recursion works.  By the time the students have Fibonacci
    working recursively, they're got at least an inkling of the
    process.

(2) why recursion can be  *horrible* choice for a solving a problem.  It
    was even better for this back in the days of 386s and the like,
    because you could have a call that went for several minutes but
    eventually came back with the right answer.

(3) how to use a static array to add memoization to a recursive function
    to get something of the best of both worlds.

[toc] | [prev] | [next] | [standalone]

#158167

Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:

> Recursive Fibonacci is actually a great function to go through in a
> beginning programming class, because you can use it to show
>
> (1) how recursion works.  By the time the students have Fibonacci
>     working recursively, they're got at least an inkling of the
>     process.
>
> (2) why recursion can be *horrible* choice for a solving a problem.
>     It was even better for this back in the days of 386s and the
>     like, because you could have a call that went for several
>     minutes but eventually came back with the right answer.
>
> (3) how to use a static array to add memoization to a recursive
>     function to get something of the best of both worlds.

I don't find these reasons persuasive.  Computing fibonacci
through double recursion is not an obvious algorithm but it is
obviously a dumb algorithm.  The lesson is not that recursion
is horrible but that bad algorithms are horrible, which in turn
removes the motivation for memoization, because it isn't really
necessary here.  (In fact I'm not sure where it is necessary,
but that's a separate discussion.)

Teaching recursion should start first with single recursion, with
a good choice being the familiar problem of greatest common
divisor.  If one then wants to give naive recursive fibonacci as
a bad example, fine, but it isn't the right place to start.  And,
if recursive fibonacci /is/ given as a bad example, it should be
closely followed by an example of double recursion where the
recursion helps rather than hurts.  Two possible choices for that
are merge sort (naturally recursive) or computing factorials of
large numbers (where subdividing recursion isn't obvious but
gives a huge speedup over the more obvious iterative algorithm).

[toc] | [prev] | [next] | [standalone]

#158171

Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Computing fibonacci through double recursion is not an obvious
> algorithm but it is obviously a dumb algorithm.

We have to define the audience when it comes to teaching this stuff. Not
everyone learns the best way with a particular approach.

In my experience, recursion "clicks" on naive Fibonacci for a lot of
students. (And it's not typically obvious to them why it's dumb; it has
to be explained.)

(The other algorithm that helps it click that I've found is floodfill.)

Fibonacci is also neat because there are multiple relatively easy ways
to solve it, and it's good for comparing and contrasting time and space
complexity while using a dirt-simple algorithm.

> Teaching recursion should start first with single recursion, with
> a good choice being the familiar problem of greatest common
> divisor.

Depends on the circles, how familiar this problem is. :)

> it should be closely followed by [...] merge sort [...] or computing
> factorials

We do this, FWIW.

-Beej

[toc] | [prev] | [next] | [standalone]

#158251

beej@beej.us (Beej) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Computing fibonacci through double recursion is not an obvious
>> algorithm but it is obviously a dumb algorithm.
>
> We have to define the audience when it comes to teaching this stuff.  Not
> everyone learns the best way with a particular approach.
>
> In my experience, recursion "clicks" on naive Fibonacci for a lot of
> students.

Using Fibonacci as an example of recursion is fine, it just
shouldn't be the first example.

> (And it's not typically obvious to them why it's dumb;  it has
> to be explained.)

I didn't mean it was obvious to people who don't yet know
anything.  We shouldn't count on /anything/ to be obvious to new
students.  But even if it isn't obvious immediately, it soon will
be, at least among those students who have an aptitude for
programming.

> (The other algorithm that helps it click that I've found is floodfill.)

I'm not sure that's a good choice.  Using recursion gives a
depth-first traversal.  For floodfill usually it's better to use
a breadth-first traversal.  In most cases I think it's mistake to
first teach an inferior version of an algorithm, and then do a
better version later.  There are exceptions to this rule, but I
don't think this is one of them.

> Fibonacci is also neat because there are multiple relatively easy ways
> to solve it, and it's good for comparing and contrasting time and space
> complexity while using a dirt-simple algorithm.

I have the sense that people think, or at least that some people
think, that it's a good idea to touch on several different
aspects at the same time, or to pull in ideas from different
levels of understanding.  No doubt there are areas where that
could be okay or perhaps even beneficial.  Recursion isn't one of
those:  it's a hugely important topic, and should not be given
short shrift, or diffused or muddled with tangential discussions,
even though the other discussions may be important in their own
right.

>> Teaching recursion should start first with single recursion, with
>> a good choice being the familiar problem of greatest common
>> divisor.
>
> Depends on the circles, how familiar this problem is. :)

I meant familiar to instructors, not necessarily to students.

>> it should be closely followed by [...] merge sort [...] or computing
>> factorials
>
> We do this, FWIW.

Good deal.

[toc] | [prev] | [next] | [standalone]

#158283

Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> For floodfill usually it's better to use a breadth-first traversal.

Interesting. Elaborate?

-Beej

[toc] | [prev] | [next] | [standalone]

#158285

beej@beej.us (Beej) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> For floodfill usually it's better to use a breadth-first traversal.
>
> Interesting.  Elaborate?

Here are two versions of a flood fill algorithm.  They are the
same except one treats the array s as a stack, the other as a
queue.  Don't worry about the "infinite" array, that will be
addressed following.  Please excuse the mixture of C and
pseudo-code.

    fill( fill-point, other stuff ){
        let s be a local array, "infinitely" large
        Index a = 0, b = 0;
        color fill-point the new color
        s[ b++ ] = fill-point
        while a < b {
            Point p = s[ --b ];
            for each neighbor, n, of p that has the old color {
                color n the new color
                s[ b++ ] = n
            }
        }
    }

    fill( fill-point, other stuff ){
        let s be a local array, "infinitely" large
        Index a = 0, b = 0;
        color fill-point the new color
        s[ b++ ] = fill-point
        while a < b {
            Point p = s[ a++ ];
            for each neighbor, n, of p that has the old color {
                color n the new color
                s[ b++ ] = n
            }
        }
    }

The queue version expands breadth first.  The stack version
expands depth first, and hence corresponds to recursion.

Of course we cannot have an "infinite" array.  In most cases a
fairly small array will suffice (a somewhat more sophisticated
algorithm helps reduce the size, but it's not important to
understand the details of that).  If the array is finite rather
than "infinite" then naturally the queue version needs to use
modulo arithmetic to keep a and b in range, but I'm sure you
can work that out so I won't go into any more detail on that.

However, with the array being finite, we need to be prepared for
the possibility that the array will fill up.  One way to do that
is have the array be allocated dynamically, using malloc/realloc
to grow the array as needed.  Another way is for fill() to call
itself recursively when s is full, with a small fixed-size array
at each level of recursion.

Which ever of the two approaches is taken, we can ask which version
(stack or queue) needs less memory resource.  It turns out that in
some pathological cases the queue version does a better job, and
AFAIK never does appreciably worse.  Also I believe (based on a
less than fully reliable memory) that the queue version does a bit
better in "typical" cases.  I don't have a reason to offer as to
why these results should be so, only that empirically that's what
I've seen.

Hopefully that is enough elaboration. :)

[toc] | [prev] | [next] | [standalone]

#158192

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Joe Pfeiffer <pfeiffer@cs.nmsu.edu> writes:
>
>> Recursive Fibonacci is actually a great function to go through in a
>> beginning programming class, because you can use it to show
>>
>> (1) how recursion works.  By the time the students have Fibonacci
>>     working recursively, they're got at least an inkling of the
>>     process.
>>
>> (2) why recursion can be *horrible* choice for a solving a problem.
>>     It was even better for this back in the days of 386s and the
>>     like, because you could have a call that went for several
>>     minutes but eventually came back with the right answer.
>>
>> (3) how to use a static array to add memoization to a recursive
>>     function to get something of the best of both worlds.
>
> I don't find these reasons persuasive.  Computing fibonacci
> through double recursion is not an obvious algorithm but it is
> obviously a dumb algorithm.  The lesson is not that recursion
> is horrible but that bad algorithms are horrible, which in turn
> removes the motivation for memoization, because it isn't really
> necessary here.  (In fact I'm not sure where it is necessary,
> but that's a separate discussion.)

A lot of students have a really hard time seeing a function as something
other than two jumps -- they trace their code as if they were taking a
jump to the start of the function, and then the return is another jump.
Talk all you want about encapsulation, parameters, abstraction...  to
the new student those are just extra complexities the professor is
layering on the two jumps.  Recursive factorial starts to get them away
from the mindset (I used to conduct an exercise in class where I'd hand
a number to the first student in the row, they'd pass n-1 to the student
on their left, they'd pass n-2 to the next student...  then the student
who got "1" would return it to the student on their right, who would
pass "2" to the next student, and so forth).  But that still doesn't
really break them of it when they're writing their code.  By the time
they've got Fibonacci working, though, they *have* to be thinking in
terms of passing (n-1) and (n-2) to the function and getting the answers
back.  It's just too hard to trace the execution without it.

> Teaching recursion should start first with single recursion, with
> a good choice being the familiar problem of greatest common
> divisor.

Fibonacci is typically the second one.  GCD is another good first one.

> If one then wants to give naive recursive fibonacci as
> a bad example, fine, but it isn't the right place to start.  And,
> if recursive fibonacci /is/ given as a bad example, it should be
> closely followed by an example of double recursion where the
> recursion helps rather than hurts.  Two possible choices for that
> are merge sort (naturally recursive) or computing factorials of
> large numbers (where subdividing recursion isn't obvious but
> gives a huge speedup over the more obvious iterative algorithm).

Mergesort would probably be a good third one.  It's got stuff going on
you need to think about other than just how the recursion works.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web