Returning from a multiple stacked call at once

[Cameron Simpson]

On 12Dec2020 17:46, ast <ast at invalid> wrote:
>Le 12/12/2020 à 09:18, Cameron Simpson a écrit :
>>On 12Dec2020 07:39, ast <ast at 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 <cs at cskk.id.au>