recursion

[Terry Reedy]

"Marc 'BlackJack' Rintsch" <bj_666 at gmx.net> wrote in message 
news:5kvbn3F5h7l3U1 at mid.uni-berlin.de...
|    f([1, 2, 3])
| r1  f([2, 3]) + [1]
| r2  f([3]) + [2] + [1]
| r3  f([]) + [3] + [2] + [1]
| r4  [] + [3] + [2] + [1]

I might help to note that the above is effectively parenthesized

( ( ([]+{3]) + [2]) +[1])

*and* that each addition (in each pair of parentheses) is done
in a different execution frame (see below).

| And now the calls return:
|
| r3  [3] + [2] + [1]
| r2  [3, 2] + [1]
| r1  [3, 2, 1]
| > [3, 2, 1]  # how this come here? how python save variables from each
| > recursion?

*Each time* a function is called, an execution frame is created(1) that is 
separate from the function object itself.  Each execution frame has its own 
set of local variables.  In particular, each has its own slices of the 
original list.

There have been languages, for instance, Fortran IV, where local variables 
were part of the function 'object' and which therefore prohibited recursion 
because of the very problem you alluded to in your question.  (My guess is 
the functions had an InUse flag that was checked when the function was 
called.)

tjr

(1) A minor variation would be for function objects to have one 
pre-allocated execution frame for non-recursive calls and others allocated 
as needed for recursive calls.