Recursion works very well with local variables because local variables are also allocated on a per-invocation basis. This means that in the case of recursion, each invocation of a recursive subroutine allocates its own columns for the local variables. When we execute code, only the rightmost columns labeled with the name of a local variable are used.
This can take some getting use to. Let us observe a fairly useless sample program.
This pseudocode generates the following trace:
| trace | A | B | C | D | E | F | G | explanation |
| comments | line# | y |
|
|||||
pre | ? |
|
||||||
| 9 | 2 |
| ||||||
| 10 | retline# | x | ||||||
| post | ? |
|
||||||
| 3 | 2 | Nothing new here! |
||||||
| (x¿1) is T | 4 |
|
||||||
| 5 | 1 |
| ||||||
| 6 | retline# | x | ||||||
| 8 | ? | There are two points to note here. First, the return line number is 8 because line 8 logically follows line 6 (we do not trace “end if”). More importantly, at this point, we have two columns labeled “x”, and both are the same local variable of the same subroutine. However, there is no confusion because only the rightmost column is accessible. In other words, only local variables created by the latest invocation is accessible. |
||||||
| 3 | 1 |
|
||||||
| (x¿1) is F | 4 |
|
||||||
| 8 | retline# | x |
|
|||||
| 8 | retline# | x |
|
|||||
post |
|
|||||||