🚀 go-pugleaf

On 04/06/2018 22:40, Joe Pfeiffer wrote:
> 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.
> 

The same way you only do a factorial calculation once. There after you 
look it up. After 32! we hit overflow so the array was short.