🚀 go-pugleaf

JRS:  In article <8ms9f2$jfg$1@kruuna.Helsinki.FI> of Wed, 9 Aug 2000
21:55:30 seen in news:borland.public.turbopascal, Osmo Ronkanen
<ronkanen@cc.helsinki.fi> wrote:
>In article <MPG.13fa0aec45dda57698970f@news.primenet.com>,
>Mike Copeland <mrcope@primenet.com> wrote:
>>
>>> (if I need to define any weird variable types, then please tell me, cos I'm
>>> really not that good with pascal)...
>>
>>   You shouldn't have to do anything of this sort..but you'll probably 
>>have to use Recursion to solve this particular problem.  Rather than post 
>>a solution for you, I suggest you investigate the concept of recursion 
>>and work out this problem as best you can.  Submit your non-working code, 
>>and someone will no doubt help you.
>
>Did you suggest using recursion to calculate Fibonacci numbers? That
>should be a felony. There is nothing as inefficient as using recursion
>to solve it.
>
>Function Fib(n:integer):longint;
>Var f1,f2,f3:longint;
>    i:integer;
>Begin
>  f1:=1;
>  f2:=1;
>  for i:=3 to n do begin
>     f3:=f1+f2;
>     f1:=f2;
>     f2:=f3;
>  End;
>  Fib:=f2;
>End;
>
>Function FibR(n:integer):longint;
>Begin
>  if n<3 then fibr:=1
>         else Fibr:=fibr(n-1)+fibr(n-2);
>End;
>
>var i:integer;
>
>Begin
>  for i:=1 to 40 do Writeln(i:5,fib(i):12);
>  for i:=1 to 40 do Writeln(i:5,fibr(i):12);
>end.
>
>The latter might look nicer, but it sure is not faster.


Speed is not everything; understanding and correctness are more
important.

Where a method is defined in a recursive manner, it is better to program
it recursively, and then to seek improvement if necessary; if the
iterative result does not agree with the recursive, one can be sure that
something is wrong.

Fibonacci is a bad example, in fact, since to the mildly experienced the
iterative and recursive approaches are both obvious; probably it should
only be used in teaching if both solutions are involved.

Neither of the two functions, as written, is good for producing the
results of your "for" loops, or for filling an array, since in each case
(although to a different extent) the same thing is calculated
repeatedly.

Where identifiably the same thing is needed repeatedly, it should be
calculated once and cached; if simple cacheing is applied to each of the
above two functions, their performances for filling the array will be
substantially improved and will become similar.  A little more
optimisation will, I think, then converge to much the same optimum,
starting in one case from the iterative and in the other from the
recursive.

Such cacheing is illustrated in Web <URL: http://www.merlyn.demon.co.uk/
programs/jad_9514.pas>, in which the problem is readily defined
recursively, there is no obvious economical iterative solution, and
actually recursing to the full is very slow; and introduction of a
simple cache produces an enormous increase in speed, IIRC.

NGs reordered, to avoid XP on the Borland server.
 
-- 
� John Stockton, Surrey, UK.  jrs@merlyn.demon.co.uk   Turnpike v4.00   MIME. �
 <URL: http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
 <URL: ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ;
 <URL: http://www.merlyn.demon.co.uk/clpb-faq.txt> Pedt Scragg: c.l.p.b. mFAQ.