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
--
http://mail.python.org/mailman/listinfo/python-list
