Software bugs aren't inevitable

[Jerzy Karczmarczuk]

Steven D'Aprano is still unhappy with the linear complexity
recursive Fibonacci I proposed as as an alternative to the cascading
recursion which for some people is "standard" or "obvious" or other
similar attribution which is not valid anymore.


> RuntimeError: maximum recursion depth exceeded
> 
> (eg calling Jerzy Karczmarczuk's efficiently recursive function with
> n=1000, while my iterative version works for at least values of n an order
> of magnitude larger.)
> 
> Yes, the maximum recursion depth in Python is an artificial limit. But
> that artificial limit is built into Python specifically to protect you
> from running into a real recursion limit based on the hardware and
> architecture of your PC, with painful consequences.

Oh, I LOVE technical solutions like that:

    "Everybody knows that you should not exceed some speed in your car.
     So, our new technology is such that if you reach 160 km per hour,
     your engine breaks.
     Surely it is an artificial limit, but it is there to protect you from
     worse problems with painful consequences."

I do not feel guilty for proposing a function which fails for n>1000.

This solution, in Haskell works for ANY n, and doesn't fill the stack
at all (provided it is strictified, i.e. the laziness does not produce
some thunk accumulation)

fib n = fibo n 0 1 where
   fibo 0 a _ = a
   fibo 1 _ b = b
   fibo n a b = fibo (n-1) b (a+b)

But tail recursion is NOT iteration in Python. So, this version:

def fib1(n,a=0,b=1):
      if n==0: return a
      elif n==1: return b
      return fib1(n-1,b,a+b)

which in a 'decent' language (no offense meant, just thinking what will
be considered scandalous in 40 years...) would run for any n, in Python
breaks for n>1000 again.  [[Terry Reedy proposed another variant; mine
is a bit shorter, perhaps a bit more elegant]].

I am sorry, but Python, as every other programming language is full of
decisions ad hoc, not always universally appreciated. Recursion can be
and IS often optimised, and tail recursion in functional languages is
entirely removed (no stack filling.) Stacks can be and are sometimes
allocated on heap, so the comment of somebody who discussed the
dichotomy stack/heap, pointing out the difference in size, may be
altogether irrelevant. Again, we, the users are not responsible for the
memory allocation policy in Python...

So, this paragraph

> Recursion is frequently extravagant in its use of resources: if nothing
> else, it takes resources to call a function, and recursion means you call
> the same function over and over again. There is a reason why functional
> programming never really took off.

is for me a biased view of the problem. Justified only by the fact that
at the beginning of functional programming (sixties) nobody cared about
the efficiency. Now, such languages as Clean, or good implementations of
Scheme are very well optimized. OCaml as well, and Haskell is improving
every 3 months. Functional languages did take off, but since a pure
functionalism requires particular, quite sophisticated techniques in
GOOD algorithm design and implementation, they are less adapted to the
brutal world than C or Python. The reasons of relatively small popularity
are much less technical than psychological, and this is KNOWN.

(Terry Hancock formulated this plainly, he prefers dumb ways because
he wants to solve problems, and he doesn't like to perform gymnastics
with his brain. We have to accept those attitudes. But I believe that
this is the effect of teaching standards; people don't learn high-level
algorithm design when they are young enough...)

====================

> If you google for Fibonacci sequences, you will find dozens,
> possibly hundreds, of implementations virtually identical to the one I
> gave. Also significant numbers of Java apps that run slow for values of n
> larger than 30 or 40 -- a good sign that they are using the naive
> algorithm.
> 
> It is a rare under-graduate or secondary school textbook that suggests
> that the naive algorithm is anything but a poor idea.

If you Google for anything, you will find hundreds of stupidities, since
nowadays the proliferation of amateurish "tutorials" etc. on the Web is
simply terrible... I WILL NOT assume the responsibility for all the bad
solutions. On the other hand, I suspect that there will be people who will
not follow this thread, who will just remember your first posting on the
subject, and they will remain convinced that recursion /per se/ is lousy,
and that your cascading algorithm is *THE* standard recursive solution.
Yes, YOU are in the state of sin! [Optional smiley here].

But, I have used myself the cascading version. It was done on purpose, in
order to get to the following solution.
[[I preferred to use a global dict, but other ways of doing it are also
possible]].

fibdic={0:0,1:1}
def fibd(n):
    if not fibdic.has_key(n):
        r=fibd(n-1)+fibd(n-2)
        fibdic[n]=r
    return fibdic[n]

And here the recursion limit won't get you!!
But the memoization techniques are rarely taught nowadays...

=====

And the story doesn't end here. There are backtracking solutions, which
in functional (lazy) languages can be emulated through co-recursion, and
in Python by the use of generators.

Jerzy Karczmarczuk