Fibonacci series recursion error

[Terry Reedy]

On 5/1/2011 5:27 AM, Hans Georg Schaathun wrote:

> Of course you do, but you are still only saying that there might be
> an application where this might happen because of excessive although
> logically correct recursion.  You have not given a single example where
> it actually happened.

I will. Stack overflow *can* happen with a bad base case. It *will* 
happen with correct linear recursion* applied to a large enough 
collection on a finite-memory machine (as opposed to an 'infinite' 
memory Turing machine).

def count_popable_collection(pop_col):
     try:
         pop_col.pop()
         return count_popable_collection(pop_col) + 1
     except (KeyError,IndexError):
         return 0

print(count_popable_collection({1,2,3}))
print(count_popable_collection([1,2,3]))

Both calls correctly print 3, but will fail for large enough sets or 
lists. I call the above body recursion*. A tail-recursive version

def count_popable_collection2(pop_col, cnt=0):
     try:
         pop_col.pop()
         return count_popable_collection2(pop_col, cnt + 1)
     except (KeyError,IndexError):
         return cnt

print(count_popable_collection2({1,2,3}))
print(count_popable_collection2([1,2,3]))

is less clear to most people, I think, and, executed as written, fails 
at the same point with the same memory error. Try either of the above 
with list(range(bignum)) (I am using 3.2).

This does not make linear recursion 'bad', just impractical for general 
use on finite-memory machines. While I consider it very useful for 
learning, it is unnecessary because it is easy to write an iterative 
version. So called tail-recursion optimization saves memory by REMOVING 
RECURSION and replacing it with iteration.

def count_popable_collection3(pop_col):
   cnt = 0
   while True:
     try:
         pop_col.pop()
         cnt += 1
     except (KeyError,IndexError):
         return cnt

print(count_popable_collection3({1,2,3}))
print(count_popable_collection3([1,2,3]))

Python does not do this automatically because 1) it can be a semantic 
change under some circumstances; 2) one who wants the iterative version 
can just as easily write it directly; and 3) Python has a better way to 
process collections that removes essentially all the boilerplate in the 
recursive-call and while-loop versions:

def count_popable_collection4(pop_col):
     cnt = 0
     for item in pop_col:
         cnt += 1
     return cnt

print(count_popable_collection4({1,2,3}))
print(count_popable_collection4([1,2,3]))


Binary recursion* is a different case because the exponential growth in 
leaf number and hence time limits the useful depth of recursion to well 
below the default of 1000.

* linear recursion: usually and at most one recursive call per call
* binary recursion: usually and at most two recursive calls per call
   Fib is the best known example.
* tail recursion: base cases return completed calculations
* body recursion: base cases return starting values, often constants

-- 

Terry Jan Reedy