On 12Dec2020 17:46, ast <ast@invalid> wrote:
>Le 12/12/2020 à 09:18, Cameron Simpson a écrit :
>>On 12Dec2020 07:39, ast <ast@invalid> wrote:
>>>In case a function recursively calls itself many times,
>>>is there a way to return a data immediately without
>>>unstacking all functions ?
>>
>>Not really. Do you have an example where this is inconvenient?
>>There are alternatives, for example passing in a Queue and put()ing
>>the data onto the queue.
[...]
>
>I don't really need it. I was just wondering and guessed it was
>not feasible.
Well, it is feasible. Kinda. Regardless, the stack need to unwind. You
_could_ abuse exceptions to do that in a single go:
class CompletedOperation(Exception):
def __init__(self, value):
self.value = value
... in your function ...
raise CompletedOperation(the_value)
... at the calling end ...
try:
call_the_function(....)
except CompletedOperation as e:
value = e.value
else:
... value not found ...
or obvious variations where that try/except it done by the outermost
function invocation, concealing it from users.
But usually you just return the value from the innermost call and return
that in turn:
def f(....):
for subpart in ... stuff ...:
value = f(subpart)
if value is not None:
return value
return None
which searches some data structure and returns nonNone on finding
something, None if not found.
>Here is a code where it would be useful. This code looks for a
>path in a graph.
>If the found path is long, say 100 nodes, then path_finder calls
>itself recursively 100 times, and has to unstack 100 times to
>provide the found path. It could be returned immediately.
The above code returns efficiently. But there's a cascade of returns.
WRT to the below code, I thought I'd restate what DL Neil has said: you
can often make these things nonrecursive by maintaining a queue or stack
of pending tasks. A recursive function keeps it state in the call stack,
but you needn't do that:
def f(node,...):
pending = [node]
while pending:
node = pending.pop(0)
if node is the one you're looking for:
return node
pending.extend(children of the node here ...)
return None
This keeps a queue of unexamined nodes in pending. You could make that a
stack by replacing the .pop(0) with .pop(). That will be more efficient
(remove the leading element of a list is comparatively expensive) but
changes the search order.
Anyway, this is what DL Neil is referring to: a nonrecursive function
with a data structure to hold the coming work, which a recursive
function would process by calling itself instead of saving the undone
task (chid nodes, here).
Cheers,
Cameron Simpson <c...@cskk.id.au>
--
https://mail.python.org/mailman/listinfo/python-list
