🚀 go-pugleaf

Charles Richmond <nume...@aquaporin4.com> writes:

> On 6/4/2018 2:05 PM, Joe Pfeiffer wrote:
>> Charlie Gibbs <cgibbs@kltpzyxm.invalid> writes:
>>
>>> On 2018-06-04, Gareth's Downstairs Computer
>>> <headstone255.but.n...@yahoo.com> wrote:
>>>
>>>> On 04/06/2018 12:13, Bob Eager wrote:
>>>>
>>>>> On Mon, 04 Jun 2018 06:28:37 -0400, Peter Flass wrote:
>>>>>
>>>>>> Gareth's Downstairs Computer
>>>>>> <headstone255.but.n...@yahoo.com> wrote:
>>>>>>
>>>>>>> On 03/06/2018 22:40, Peter Flass wrote:
>>>>>>>>
>>>>>>>> Some problems are easily solved by recursion that are significantly
>>>>>>>> more complicated otherwise.
>>>>>>>
>>>>>>> I would be interested to know some examples, please?
>>>>>>
>>>>>> Depth-first search of a binary tree. Top-down parsing.
>>>>>>
>>>>>> Anything that requires retracing a path thru a data structure. Without
>>>>>> recursion you have to maintain a table to keep track of where you've
>>>>>> been and where you're going. Recursion just handles it naturally.
>>>>>
>>>>> +1
>>>>
>>>> In both cases a table is maintained, either through a manually
>>>> programmed (trivial) table or through the auto-maintained call
>>>> tree, either by a return stack, or, again, in the case of
>>>> languages such as PL/M-86 that allocate local data statically,
>>>> a human-maintained call structure.
>>>>
>>>> It seems to me that computer scientists wish for everything to
>>>> be handed to them on a plate and baulk at the thought of
>>>> minor diversions to provide some simple and trivial extra facitlites
>>>> whereas real world programmers just get on with the job.
>>>
>>> I admit that there are probably cases where recursion is an
>>> elegant solution to the problem.  However, in my experience
>>> such cases are few and far between.  I've always considered
>>> an obsession with recursion to be a hallmark of the CS weenie.
>>
>> Speaking as retired faculty, we tend to be better at giving the students
>> tools than at showing them where they're appropriate...
>>
>> In the case of recursion, a problem a lot of new students have is
>> understanding the difference between calling a function, and using a
>> goto to get to the function and another goto to go back where you came
>> from (I actually once had a student ask me what the difference was; he
>> didn't have enough of a concept of abstraction, encapsulation, or
>> organization for any answer in those terms to make the slightest
>> sense).  Simply not telling them about labels and gotos in the first
>> class helps, but there's always one who figures it out on his own and
>> turns in a bowl of amazing spaghetti for his second or third assignment.
>>
>> By the time they can get a simple recursive function to work, they have
>> to have some sort of understanding of the notion of a function call
>> being the same thing as turning a part of the problem over to somebody
>> else to solve, and getting an answer back.  So it's really helpful in
>> teaching functions.
>>
>> Unfortunately, they also tend to come out of the experience with the
>> idea that it's a great way to find the fibonacci sequence...
>>
>
> If you use "dynamic programming" and cache the results of Fibonacci
> calls, it can be quite efficient.  When the Fibonacci function returns
> a result or sub-result (say the fifth Fibonacci number), the result is
> cached.  Before any call to the Fibonacci function, the program first
> checks to see if the result being sought...  already exists in the
> cache.  If the result is in the cache, use the result instead of
> calling the function.
>
> This prevents repetitiously calling of the Fibonacci function for any
> one particular number.  For example, if you have already called the
> Fibonacci function for the tenth number...  the result will be in the
> cache.  You never again need to call the Fibonacci function for the
> tenth Fibonacci number.

Of course.  But in context it's clear I'm talking about a naive
recursive implementation.