Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Recursion v Memoization Date: Thu, 07 Jan 2021 04:54:05 -0800 Organization: A noiseless patient Spider Lines: 62 Message-ID: <86tursq55e.fsf@linuxsc.com> References: <861rf6uzw4.fsf@linuxsc.com> <1b1rf2zsuf.fsf@pfeifferfamily.net> <86h7nwrq8s.fsf@linuxsc.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="c154dc4d172b443324888acc44505703"; logging-data="15968"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18v58mQ0IARzoCFMASxpBx1IUgzFVMXgNQ=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:svg0ioZdlgKUrtM7p6wIfP1pbgc= sha1:buZeCWdKXMlK6LVMJp6pKCRDgK0= Xref: csiph.com comp.lang.c:158251 beej@beej.us (Beej) writes: > Tim Rentsch 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.