🚀 go-pugleaf

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.

-- 
numerist at aquaporin4 dot com