Returning from a multiple stacked call at once

[dn]

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