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

Groups > comp.lang.c > #158251

Re: Recursion v Memoization

Show all headers | View raw

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.

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