Iterative vs. Recursive coding

[Tim Chase]

On 08/21/10 04:35, Baba wrote:
> On Aug 21, 7:37 am, John Nagle<na... at 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