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

Groups > comp.lang.c > #158252

Re: Recursion v Memoization

Show key headers only | View raw

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

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

That's a good exercise.  As it happens I used a similar exercise
(but not about recursion or factorial) many years ago when
teaching a programming class.

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

Having there be two recursive calls is significant.  I may have
a better example problem for that - see below.

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

It's good to hear we agree on the main point.  At first I thought
you meant start off with Fibonacci.

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

In light of this additional information, let me offer a more
refined set of suggestions.

Start with GCD.  That will get the students used to the form of
recursion, even if some of them will not yet understand it.

Next do factorial, but actually three different factorials.
First the obvious one:

   unsigned
   factorial_one( unsigned n ){
      return  n < 2  ? 1  : n * factorial_one( n-1 );
   }

Second, a version that transforms the first version into a two
argument form so that tail recursion can be used:

   static unsigned factorial_times( unsigned, unsigned );

   unsigned
   factorial_two( unsigned n ){
      return  n < 2  ? 1  : factorial_times( n, 1 );
   }

   unsigned
   factorial_times( unsigned n, unsigned m ){
      return  n < 2  ? m  : factorial_times( n-1, n*m );
   }

Third, a different approach using subdivision, which gives two
recursive calls rather than just one:

   static unsigned times_from_to( unsigned k, unsigned n );
   /* product of integers i with k <= i < n */

   unsigned
   factorial_three( unsigned n ){
      return  n < 2  ? 1  : times_from_to( 1, n+1 );
   }

   static unsigned
   times_from_to( unsigned k, unsigned n ){
      unsigned delta = n-k;
      unsigned m = k + delta/2;

      return  delta < 2  ? k  : times_from_to( k, m ) * times_from_to( m, n );
   }

(As mentioned above the point of this approach is for cases where
multiple precision arithmetic is being used, so that when two
numbers are multiplied they have similar magnitudes, which makes
the computation go a lot faster.)

After the three factorials, fibonacci, if that is thought
necessary.  (I'm undecided about that.)

For the last example, not mergesort, but the Chinese Ring puzzle.
The problem is pretty much inherently recursive (I don't see any
obvious way to turn it into an iteration).  Also it uses mutual
recursion, with 'ring_on()' and 'ring_off()' each calling the
other.  Furthermore it gives an exponential cost because the
problem itself is exponential.  (I didn't think up this example
myself but heard it from Professor Don Stanat, if I remember
right.)  I'm sure there are other good examples of problems that
use mutual recursion, but offhand I can't think of one that is
not amenable to being turned into an iteration.

So, fwiw, there are some ideas.

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