Recursive calls and stack

[jm.suresh]

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]

En Wed, 14 Feb 2007 03:09:37 -0300, (e-mail address removed)

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/

 

[jm.suresh]

En Wed, 14 Feb 2007 03:09:37 -0300, (e-mail address removed)


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/

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]

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]

En Wed, 14 Feb 2007 04:23:46 -0300, (e-mail address removed)

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:

py> def test():
.... x = 22
.... y = 33
.... z = x+y
.... return anotherFunction(z)
....
py> def anotherFunction(z):
.... print "previous frame:", sys._getframe(1).f_locals
....
py> test()
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.

 

[Terry Reedy]

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:
500

Terry Jan Reedy

 

[Neil Cerutti]

En Wed, 14 Feb 2007 03:09:37 -0300, (e-mail address removed)


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.

 

[Gabriel Genellina]

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 recursion optimisation
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").

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...

 

[Szabolcs Nagy]

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.setrecursionlimit(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.deque is faster
for stack (and especially for queue) data structure than list.

 

[Neil Cerutti]

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.

 

[Gabriel Genellina]

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.

 

[Neil Cerutti]

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."

 

[Gabriel Genellina]

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.

 

[Neil Cerutti]

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.