Fibonacci series recursion error

Hans Georg Schaathun hg at schaathun.net
Sat Apr 30 07:50:45 CEST 2011


On Fri, 29 Apr 2011 23:45:30 -0500, harrismh777
  <harrismh777 at charter.net> wrote:
:  There is much debate about this generally, but general wisdom is that 
:  recursion is to be avoided when possible.

That is context dependent at best.  You have given reasons to avoid
recursion in /executable code/, but that's a compiler issue.  You
have only given reason /for/ recursion in source code.  It generally
gives little and very reaadble code.  In almost every non-trivial
software project, the programmers will be more overworked than the
computer, and therefore they are the once to consider when optimising.

:  Recursion is very tempting to young artists because its a ~cool trick, 
:  and because sometimes it requires very little coding (although huge 
:  amounts of memory!),  or as in your case, recursion depth errors.

Waste of memory happens only with some types of recursion, and even
then it is usually negligible.  The recursion depth issue is the
result of a flawed base case, and nothing to do with a weakness of
recursion.

:  Anyway, the better way to build a Fibonacci sequence generator is the 
:  following... I have expanded things a bit so that someone not knowing 
:  what the sequence is can see what is happening... you will notice simple 
:  'for' iterations, and no recursion:

And surprisingly difficult to read for such a well-known operation as
Fibonacci numbers.  If you want to promote iteration, you had better
at least try to make it legible.

Your code is obviously more efficient in being O(n) whereas OP had
(I think) O(2^n), but that's not a property of iteration.  You can
make a recursive implementation which is O(n).  Any undergraduate 
textbook teaching recursion in any depth is likely to give it as an 
example; see e.g. Simon Thompson's Haskell book.

-- 
:-- Hans Georg



More information about the Python-list mailing list