Can a subroutine invoke itself? The answer is “technically, yes”. This is because if this is not done right, it can lead to endless invocations. If done right, however, this form of invocation, called “recursion”, is actually a powerful programming technique.
Let us observe the following example:
This pseudocode yields the following trace.
| A | B | C | D | E | explanation |
|
trace | comments | line# | x |
|
||
| 1 | pre | ? |
|
|||
| 2 | 10 | 2 |
| |||
| 3 | 11 | retline# | This is a “regular” invocation. |
|||
| 4 | post |
|
||||
| 5 | (x ≤ 1) is F | 2 |
|
|||
| 6 | 5 | 1 |
| |||
| 7 | 6 | retline# | This is invoking from the subroutine itself. Note that the mechanism of invoking does not change. Line 8 of the pseudocode is the line that logically follows line 6. |
|||
| 8 | 8 |
|
||||
| 9 | (x <= 1) is T | 2 | Because an invocation of a subroutine always starts on the first action line of a subroutine, we continue execution on line 2 of the pseudocode. |
|||
| 10 | 3 | 20 |
|
|||
| 11 | 8 | retline# | The mechanism of ending a subroutine (returning from a subroutine) also does not change. If the “retline#” column says go to line 8 to continue execution, we just do so, even though we are on line 8 right now. |
|||
| 12 | 8 | retline# | What is line 8? It is the end of a subroutine. We use exactly the same mechanism to return from the first invocation of the subroutine. |
|||
| 13 | post |
|
||||
One of the most important point to remember is that the mechanism of invoking a subroutine does not a bit when we are invoking from the invoked subroutine itself.
It is also important to note that the allocation and deallocation of the “retline#” column is done on a per invocation basis, and not on a per subroutine basis. This point is important because the per-invocation basis makes recursion possible.