On 08/21/10 04:35, Baba wrote:
On Aug 21, 7:37 am, John Nagle<na...@animats.com> wrote:
On 8/20/2010 1:17 PM, John Bokma wrote:
I think you mean tail recursion optimization / elimination.
Python does tail recursion:
Not very well.
def cnt(n) :
if n> 0 :
cnt(n-1)
I'm intrigued by this example. Is there something missing in the code?
When i run it i get:<function cnt at 0x02B2FE70>
I suppose it is meant to print a sequence of numbers from n down to
zero?
Sounds like you merely executed:
>>> cnt
<function cnt at 0xDEADBEEF>
which just asks what "cnt" is (in this case, it is as Python
reports: a function named "cnt" at some given address), instead
of actually *running* the function:
>>> cnt(42)
(function-calling is performed by the parens).
re tail recursion, on wiki i found:
"With tail recursion, there is no need to remember the place we are
calling from—instead, we can leave the stack alone, and the newly
called function will return its result directly to the original
caller. Converting a call to a branch or jump in such a case is called
a tail call optimization. "
not sure i understand that...
is this bit of theory applicable to your cnt function above?
The recursive call (calling cnt(...) again) is the last
instruction in the function before it would otherwise exit. A
tail-recursion-aware compiler/interpreter would optimize that
away. Instead of keeping track of a new stack-frame for each
call (growing in stack-memory usage with each call), it would
recognize that it could just reuse the current/top stack-frame to
prevent stack blowouts.
JohnN's observation was that Python doesn't recognize
tail-recursion, and thus blows the top of the default stack-size
at 999 recursive calls (a number adjustable with parameters to
Python). If Python recognized tail-recursion and optimized for
it, you could use any number you had the time to wait for.
-tkc
--
http://mail.python.org/mailman/listinfo/python-list
