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 2 of 2 — ← Prev page 1 [2]

#158193

On 05/01/2021 21:35, Joe Pfeiffer wrote:
>
> 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.


Factorial!

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

#158198

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

> On 05/01/2021 21:35, Joe Pfeiffer wrote:
>>
>> 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.
>
>
> Factorial!

That's what I pointed to as a good first one.

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

#158212

On Tue, 2021-01-05, Joe Pfeiffer wrote:
...
> 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.

I can imagine that 30 years ago, when the students had toyed with
BASIC, but now?  Jumping is not /that/ natural: I haven't thought of
program flow that way since the early 1990s.

If they are thinking that way today, it would be interesting to
learn where they get it from.

Or do they get 

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

Seems sensible.

CS educations around here tend to start with a functional language
(Standard ML or LISP in my days, Haskell now I guess) so that 





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


-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

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

#158221

On Wed, 2021-01-06, Jorgen Grahn wrote:
> On Tue, 2021-01-05, Joe Pfeiffer wrote:
> ...
>> 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.
>
> I can imagine that 30 years ago, when the students had toyed with
> BASIC, but now?  Jumping is not /that/ natural: I haven't thought of
> program flow that way since the early 1990s.
>
> If they are thinking that way today, it would be interesting to
> learn where they get it from.
...

And then I wrote some unfinished thoughts and posted the whole thing.
Sorry; please ignore.

(Never post to Usenet from some awkward and unfamiliar console while
installing the computer.)

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

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

#158252

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.

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

#157935

On 12/29/2020 1:30 PM, Real Troll wrote:
> We sometimes resort to using simple methods such as Recursion functions 
> or  interactive functions ...

The word you were looking for is "iterative".

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web