Returning from a multiple stacked call at once
dn
PythonList at DancesWithMice.info
Sat Dec 12 15:33:18 EST 2020
On 13/12/2020 05:46, ast 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. It's quite dependent on what you're trying to do
>> though.
>
> I don't really need it. I was just wondering and guessed it was
> not feasible.
[somewhat simplified]
The way Python handles recursion is to add a "frame" every time the
function is called. The "frame" contains all the data-items for the
function. Think of the frames as stacked on top of each other:
frame n
frame n+1
frame n+2
...
NB you can 'see' this when viewing an exception tracing its way from a
deeply-nested function, to the function which called it, to the function
which called that, etc.
This is how node-1's attributes are kept separate from node-2's. If you
think that only the 'current frame' as being visible at any stage of the
program's execution, it will suit our purposes for-now.
One effect of a "return" is to close the current frame (and to carry any
return-value 'back' to the previous frame).
Per comment (below), if this function recurses 100 times, then there
will be 100 frames. Accordingly, there need to be 100 returns to close
each of those frames.
NB Python offers reflective facilities to inspect all of this, if you
really want to see what happens 'under the hood/bonnet'.
> 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.
> ...
Recursion may not be the best tool/tactic here. As you observe, it has
to be 'unwound'!
Assuming the objectives are:
1 trace through a graph
2 locate an identified node
3 note (and make available 'later') the path through the graph to reach
said node.
The logic for (1) and (2) has been done.
For (3), consider using a "stack". This is a ComSc term (in case you've
not studied such), and is the same concept as the 'stack of frames' (above).
1 Create a list "stack".
2 Walk the network.
3 Upon 'arrival' at a node, add the node to the 'stack' by appending
relevant detail(s) to the list.
4 If the node is 'the end', stop walking.
If the 'walk' is a loop (cf recursion), the 'stop' becomes a (single)
"break".
If the identified node is found 50-nodes 'in', or 100-nodes, that will
be the length of the list/stack. (which BTW will require less storage
than the same number of recursion-frames)
Now, back to ComSc (again, with apologies for appearing to 'talk-down',
if you've studied this stuff but let's help anyone else 'following along
at home'), when it comes to using the list/stack, if you start with the
found-node and work your way 'back' to the start-node, this will require
working from the list[ -1 ] element, back to the zero-th element.
Accessing each element is known as "popping the stack", and you will
find a Python list.method() enacting such - but be careful about the
working-backwards logic!
Conversely, if the ensuing functionality wants to 'start' from the
start-node and walk 'forward' through the graph to the found-node; then
that process will start at list[ 0 ], per most collection-processing. In
which case, rather than a "stack", we are looking at a "queue" (per
@Cameron).
Thus, a "stack" accepts additions to 'the end', and "pops" data from the
same 'end' ("LIFO" = last-in, first-out). Whereas a "queue" also adds to
'the end', but processes/pops from the beginning ("FIFO" = first-in,
first-out).
If this ComSc-stuff is 'new', then plenty of books and web-sites discuss
such data-structures...
--
Regards =dn
More information about the Python-list
mailing list