Recursive calls and stack

[jm.suresh@no.spam.gmail.com]

Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill the stack space with the local
variables inside each call. If this is not good, is there a better way
to implement? Or python itself will understand that the calls happen
in the last line, so local variables need not be pushed into the
stack?

def find_point(pt):
return _hor_search(pt, random_obj)

def _hor_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _ver_search(pt, object)

def _ver_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _hor_search(pt, object)


-
Suresh

[Gabriel Genellina]

Re: Recursive calls and stack

En Wed, 14 Feb 2007 03:09:37 -0300, jm.suresh@no.sp am.gmail.com
<jm.suresh@gmai l.comescribió:

Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill the stack space with the local
variables inside each call. If this is not good, is there a better way
to implement? Or python itself will understand that the calls happen
in the last line, so local variables need not be pushed into the
stack?

I'm afraid not, the calls will be stacked until some object is found.
Python does not do "tail recursion optimization" (at least, I'm not aware
of that). But even if it could do that, in this case you have recursive
calls between two functions, and that's a bit harder.

Going back to your original problem, maybe you can use some known
algorithms from computational geometry; start with

http://www.faqs.org/faqs/graphics/algorithms-faq/

--
Gabriel Genellina

[jm.suresh@no.spam.gmail.com]

Re: Recursive calls and stack

On Feb 14, 11:45 am, "Gabriel Genellina" <gagsl...@yahoo .com.ar>
wrote:

En Wed, 14 Feb 2007 03:09:37 -0300, jm.sur...@no.sp am.gmail.com
<jm.sur...@gmai l.comescribió:
>

Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill the stack space with the local
variables inside each call. If this is not good, is there a better way
to implement? Or python itself will understand that the calls happen
in the last line, so local variables need not be pushed into the
stack?

>
I'm afraid not, the calls will be stacked until some object is found.
Python does not do "tail recursion optimization" (at least, I'm not aware
of that). But even if it could do that, in this case you have recursive
calls between two functions, and that's a bit harder.
>
Going back to your original problem, maybe you can use some known
algorithms from computational geometry; start with http://www.faqs.org/faqs/graphics/algorithms-faq/
>
--
Gabriel Genellina

Thanks Gabriel for the response.

I am OK with calls being stacked, but I wondering will the local
variables be stacked given that return statement is followed by the
function call?

def test():
x = 22
y = 33
z = x+y
return anotherFunction (z)

In this function will all the local variables (x,y,z) be pushed into
the stack before calling anotherFunction (z) or Python will find out
that the locals are no longer needed as anotherFunction (z) is just
returned?

-
Suresh

[jm.suresh@no.spam.gmail.com]

Re: Recursive calls and stack

On Feb 14, 11:09 am, "jm.sur...@no.s pam.gmail.com"
<jm.sur...@gmai l.comwrote:

Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill thestackspace with the local
variables inside eachcall. If this is not good, is there a better way
to implement? Orpythonitself will understand that the calls happen
in the last line, so local variables need not be pushed into thestack?
>
def find_point(pt):
return _hor_search(pt, random_obj)
>
def _hor_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _ver_search(pt, object)
>
def _ver_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _hor_search(pt, object)
>
-
Suresh

I found a simpler solution: get rid of recursive calls; using while
loops.

-
Suresh

[Gabriel Genellina]

Re: Recursive calls and stack

En Wed, 14 Feb 2007 04:23:46 -0300, jm.suresh@no.sp am.gmail.com
<jm.suresh@gmai l.comescribió:

I am OK with calls being stacked, but I wondering will the local
variables be stacked given that return statement is followed by the
function call?
>
def test():
x = 22
y = 33
z = x+y
return anotherFunction (z)
>
In this function will all the local variables (x,y,z) be pushed into
the stack before calling anotherFunction (z) or Python will find out
that the locals are no longer needed as anotherFunction (z) is just
returned?

Not exactly like "pushed into the stack", but there exists a frame object,
and it contains references to its local variables, and will be alive until
anotherFunction returns. From inside anotherFunction you can even inspect
those variables:

pydef test():
.... x = 22
.... y = 33
.... z = x+y
.... return anotherFunction (z)
....
pydef anotherFunction (z):
.... print "previous frame:", sys._getframe(1 ).f_locals
....
pytest()
previous frame: {'y': 33, 'x': 22, 'z': 55}

So x,y,z will still be there until anotherFunction actually returns to
test, and the frame object is disposed. For a highly recursive function,
that's bad news. For debugging normal programs, that's good news; the
cgitb module, by example, is able to show the values for local variables
in all previous frames when an exception is raised.

--
Gabriel Genellina

[Terry Reedy]

Re: Recursive calls and stack


"jm.suresh@no.s pam.gmail.com" <jm.suresh@gmai l.comwrote in message
news:1171437825 .977798.249420@ q2g2000cwa.goog legroups.com...
I am OK with calls being stacked, but I wondering will the local
variables be stacked given that return statement is followed by the
function call?

def test():
x = 22
y = 33
z = x+y
return anotherFunction (z)

In this function will all the local variables (x,y,z) be pushed into
the stack before calling anotherFunction (z) or Python will find out
that the locals are no longer needed as anotherFunction (z) is just
returned?
=============== ==
To add to Gabriel's answer:

Questions of this sort are implementation specific. CPython will allocate
the objects on the heap. But I believe at present something will go on the
C stack with each function call. I suspect that the C array that typically
implements the local namespace is included but don't specifically know.
The local names are deleted, and the associated heap objects released if
that make the reference count 0, as part of the return process. No
optimization of the sort you indicate is done. Indeed, the heap objects
could have other references, and the namespace array is fixed size, so I am
not sure there is anything that could, in general, be done. In any case,
Python never deletes without at least implicit instruction to do so.

The maximun recursion depth CPython will attempt is governed by an internal
variable that you can get and set to adjust to your problem and hardware:

>>sys.getrecurs ionlimit()

1000

>>sys.setrecurs ionlimit(500)
>>sys.getrecurs ionlimit()

500

Terry Jan Reedy

[Neil Cerutti]

Re: Recursive calls and stack

On 2007-02-14, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

En Wed, 14 Feb 2007 03:09:37 -0300, jm.suresh@no.sp am.gmail.com
><jm.suresh@gma il.comescribió:

> Is this way of implementation fill the stack space with the
> local variables inside each call. If this is not good, is
> there a better way to implement? Or python itself will
> understand that the calls happen in the last line, so local
> variables need not be pushed into the stack?

>
I'm afraid not, the calls will be stacked until some object is
found. Python does not do "tail recursion optimization" (at
least, I'm not aware of that).

To be just a little pedantic, it's "tail call optimization". Any
tail call can be optimized, not just recursive ones.

But even if it could do that, in this case you have recursive
calls between two functions, and that's a bit harder.

So the effect is that mutual recursion isn't actually any harder.

Moreover, if his functions calls really are tail-calls, then
translating them by hand into iteration might be fairly easy.

A simple, silly example:

def sum(seq):
if len(seq) == 0:
return 0
else:
return seq[0] + sum(seq[1:])

Above, sum is not a tail call, since the + operation must be
"defered" until after the call to sum returns.

Below, sum is a tail call.

def sum(seq, accum=0):
if len(seq) == 0:
return accum
else:
return sum(seq[1:], accum+s[0])

Since no state must be retained by sum when calling sum, it's a
tail call. The last version translates more or less directly into
a dumb while loop.

I don't believe Python does tail call optimization; at least it
isn't document that it does it.

--
Neil Cerutti
The audience is asked to remain seated until the end of the recession.
--Church Bulletin Blooper

[Gabriel Genellina]

Re: Recursive calls and stack

En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti <horpner@yahoo. com>
escribió:

On 2007-02-14, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

>Python does not do "tail recursion optimization" (at
>least, I'm not aware of that).

>
To be just a little pedantic, it's "tail call optimization". Any
tail call can be optimized, not just recursive ones.

Maybe, but I didn't invent the term:

http://computing-dictionary.thefreedictionary.com/tail%20recursion%20optimisation

It's true that tail recursion is a special case of tail call - but it's
just the case that can be managed by hand, no special support on the
language -trampoline or whatever- is required (just a loop, "GOTO 1").

>But even if it could do that, in this case you have recursive
>calls between two functions, and that's a bit harder.

>
So the effect is that mutual recursion isn't actually any harder.

But some kind of language support is required in this case. At least I
don't know how to handle mutual recursion (apart from inlining one
function inside the other...). But I'm certainly not a "program
transformation guru" (neither a novice!) so I would not be surprised if
someone says it can be done...

--
Gabriel Genellina

[Szabolcs Nagy]

Re: Recursive calls and stack


jm.suresh@no.sp am.gmail.com wrote:

Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
...

in case you ever need deeply nested recursion:
one solution is to use the already mentioned sys.setrecursio nlimit(n)
another is to use your own stack

dummy example:

def fact_recursive( n):
if n>0:
return fact_recursive( n-1)*n
else:
return 1

def fact_iterative( n):
stack = []
while n 0:
stack.append(n)
n -= 1
ret = 1
while stack:
ret *= stack.pop()
return ret

actually you can always rewrite recursion with a stack and iterations

note that if you use version >= 2.4, then collections.deq ue is faster
for stack (and especially for queue) data structure than list.

[Neil Cerutti]

Re: Recursive calls and stack

On 2007-02-15, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti <horpner@yahoo. com>
escribió:

>So the effect is that mutual recursion isn't actually any
>harder.

>
But some kind of language support is required in this case. At
least I don't know how to handle mutual recursion (apart from
inlining one function inside the other...). But I'm certainly
not a "program transformation guru" (neither a novice!) so I
would not be surprised if someone says it can be done...

What happens (using the model of an imaginary virtual machine,
perhaps like the Python interpreter) is the following.

A normal function call pushes a call-frame onto a stack. The
call-frame contains information necessary for returning from the
function, and usually a place to store its local variables and
parameters.

A function called in "tail" position simply overwrites the
current call-frame with the new one instead of pushing it onto
the stack.

--
Neil Cerutti
The church will host an evening of fine dining, superb entertainment, and
gracious hostility. --Church Bulletin Blooper

[Gabriel Genellina]

Re: Recursive calls and stack

En Thu, 15 Feb 2007 13:37:19 -0300, Neil Cerutti <horpner@yahoo. com>
escribió:

On 2007-02-15, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

>En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti <horpner@yahoo. com>
>escribió:

>>So the effect is that mutual recursion isn't actually any
>>harder.

>>
>But some kind of language support is required in this case. At
>least I don't know how to handle mutual recursion (apart from
>inlining one function inside the other...). But I'm certainly
>not a "program transformation guru" (neither a novice!) so I
>would not be surprised if someone says it can be done...

>
What happens (using the model of an imaginary virtual machine,
perhaps like the Python interpreter) is the following.
>
A normal function call pushes a call-frame onto a stack. The
call-frame contains information necessary for returning from the
function, and usually a place to store its local variables and
parameters.
>
A function called in "tail" position simply overwrites the
current call-frame with the new one instead of pushing it onto
the stack.

This is the "kind of language support" menctioned. For tail recursion you
don't require that support.

--
Gabriel Genellina

[Neil Cerutti]

Re: Recursive calls and stack

On 2007-02-15, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

En Thu, 15 Feb 2007 13:37:19 -0300, Neil Cerutti <horpner@yahoo. com>
escribió:
>

>On 2007-02-15, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

>>En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti <horpner@yahoo. com>
>>escribió:
>>>So the effect is that mutual recursion isn't actually any
>>>harder.
>>>
>>But some kind of language support is required in this case. At
>>least I don't know how to handle mutual recursion (apart from
>>inlining one function inside the other...). But I'm certainly
>>not a "program transformation guru" (neither a novice!) so I
>>would not be surprised if someone says it can be done...

>>
>What happens (using the model of an imaginary virtual machine,
>perhaps like the Python interpreter) is the following.
>>
>A normal function call pushes a call-frame onto a stack. The
>call-frame contains information necessary for returning from the
>function, and usually a place to store its local variables and
>parameters.
>>
>A function called in "tail" position simply overwrites the
>current call-frame with the new one instead of pushing it onto
>the stack.

>
This is the "kind of language support" menctioned. For tail
recursion you don't require that support.

I'm not sure what you mean. The above support is enough for tail
recursion, mutual recursion, and any other tail call to be
"optimized. "

--
Neil Cerutti

[Gabriel Genellina]

Re: Recursive calls and stack

En Thu, 15 Feb 2007 16:35:25 -0300, Neil Cerutti <horpner@yahoo. com>
escribió:

On 2007-02-15, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

>En Thu, 15 Feb 2007 13:37:19 -0300, Neil Cerutti <horpner@yahoo. com>
>escribió:
>>

>>On 2007-02-15, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:
>>>En Wed, 14 Feb 2007 10:41:53 -0300, Neil Cerutti <horpner@yahoo. com>
>>>escribió:
>>>>So the effect is that mutual recursion isn't actually any
>>>>harder.
>>>>
>>>But some kind of language support is required in this case. At
>>>least I don't know how to handle mutual recursion (apart from
>>>inlining one function inside the other...). But I'm certainly
>>>not a "program transformation guru" (neither a novice!) so I
>>>would not be surprised if someone says it can be done...
>>>
>>What happens (using the model of an imaginary virtual machine,
>>perhaps like the Python interpreter) is the following.
>>>
>>A normal function call pushes a call-frame onto a stack. The
>>call-frame contains information necessary for returning from the
>>function, and usually a place to store its local variables and
>>parameters.
>>>
>>A function called in "tail" position simply overwrites the
>>current call-frame with the new one instead of pushing it onto
>>the stack.

>>
>This is the "kind of language support" menctioned. For tail
>recursion you don't require that support.

>
I'm not sure what you mean. The above support is enough for tail
recursion, mutual recursion, and any other tail call to be
"optimized. "

I only want to say that tail *recursion* can be eliminated trivially
transforming the code into a while loop, and that can be done by the
programmer, and doesn't require compiler support. Head *recursion* can be
eliminated too by using some storage as temporary stack, and that doesn't
require external support either. Mutual recursion (and generic tail call
elimination) require some sort of external support: one can't eliminate
the call just by transforming the program.

--
Gabriel Genellina

[Neil Cerutti]

Re: Recursive calls and stack

On 2007-02-15, Gabriel Genellina <gagsl-py@yahoo.com.ar wrote:

>I'm not sure what you mean. The above support is enough for
>tail recursion, mutual recursion, and any other tail call to
>be "optimized. "

>
I only want to say that tail *recursion* can be eliminated
trivially transforming the code into a while loop, and that
can be done by the programmer, and doesn't require compiler
support. Head *recursion* can be eliminated too by using some
storage as temporary stack, and that doesn't require external
support either. Mutual recursion (and generic tail call
elimination) require some sort of external support: one can't
eliminate the call just by transforming the program.

Ah, I see now. Had my blinders on.

--
Neil Cerutti
Low Self-Esteem Support Group will meet Thursday at 7 to 8:30 p.m. Please use
the back door. --Church Bulletin Blooper