Why does saving addresses on a stack give us the only way out for both nesting and "recursing" subroutines? [closed]

Question

My text (Computer Organization and Embedded Systems, 6e, by Hamacher et al.) poses the following:

Consider the following possibilities for saving the return address of a subroutine:
(a) In a processor register
(b) In a memory location associated with the call, so that a different location is used when the subroutine is called from different places
(c) On a stack

and says that the answer options are:

(a) Neither nesting nor recursion are supported.
(b) Nesting is supported, because different Call instructions will save the return address at different memory locations. Recursion is not supported.
(c) Both nesting and recursion are supported.

I cannot understand the comment regarding (b).

Suppose our solution was (a).

This works for a case where we go "one level deep" but if we nest or recurse then everything except the very last calling function will have the correct returning address clobbered. No problem.

But what of (b)? Is the proposition that every subroutine call would cause the address of the next instruction after the call to be stored somewhere which is a (injective) function of the memory address of the call? If so, where does the problem arise with recursion? I think maybe I'm not getting my arms around even what we're talking about when we say "memory location associated with the call".

Answer 1

This one is easy. It says "(b) In a memory location associated with the call, so that a different location is used when the subroutine is called from different places".

In the case of recursion, successive calls may come from the same place.

added

No one said that the machine architecture for case (b) makes a lot of sense or is an easy one to construct and make functional.

But suppose there exists a special 8-bit return address key register called X0 that the return instruction uses and suppose a call instruction performs the following steps:

1. TEMP = HASH8(subroutine address, call instruction address)

   Here, HASH8 is some hardware block that generates an 8-bit hash code from the 16-bit subroutine address and the 16-bit target address of the call instruction.

   It is assumed to be unlikely that the same HASH8 generates unwanted collisions (given whatever justification someone comes up with.)

   However, the same call located at the same instruction address making a call to the same subroutine will produce the same HASH8.

2. R[TEMP]= 16-bit return address from call

   R[] is a 16-bit wide data memory with an 8-bit address.

3. X[TEMP]= X0

   X[] is an 8-bit wide data memory with an 8-bit address.

4. X0 = TEMP

5. PC = 16-bit address of called subroutine

Suppose the return instruction performs:

1. TEMP = X0

2. X0 = X[TEMP]

3. PC = R[TEMP]

Don't ask me why anyone would do it this way. I just made it up. But it does match case (b) in your example.

Hopefully, now you can see the problem with recursion in a situation posed by case (b).

By the way, the HP21xx series of CPUs would literally blow away the first address of any called subroutine with the return address of the caller. (No stacks here!) A subroutine would look something like this:

FDATE   NOP             This location gets overwritten with return address of caller.
        LDA FILE#       Subroutine always starts here.
        SSA,RSS
        .
        .
        .
        JMP FDATE,I     Return from call.

All calls blow away the first address with the return address and then always start the subroutine at addr+1.

Now, that certainly doesn't support recursion!