What properties must a language have to support recursion?

Question

I was studying about recursion and I came across this question:

FORTRAN implementations do not permit recursion because

a. they use static allocation for variables

b. they use dynamic allocation for variables

c. stacks are not available on all machines

d. it is not possible to implement recursion on all machines.

I found out that the answer was (a)

But I want to know all the features that a programming language should have to support the recursion.

Can somebody please solve my doubt

Thanks in advance

Answer 1

Local variables in a function or subroutine (including its return address) should be a fresh copy whenever it is called.

Usually this is done using a stack architecture. Whenever a function is called, its arguments are pushed on the stack, then its return address is pushed, then a block of memory is also "pushed" (by decrementing the stack pointer by a sufficient amount). A special register, the "frame pointer" is set pointing to that memory, and the function refers to all its local variables by reference to that register.

Other languages do not use a physical hardware stack, but a logical one implemented as a linked list, but the principle is the same.

Since the original Fortrans did not have this concept, and stored all variables at fixed global locations, a recursive call would crash or hang. For example, if A calls B calls C calls B, then B returns to C, which returns to B, which returns to C, ad infinitum, because B can only remember one return address.

calls:  A -> B -> C -> B

returns:     B <- C <- B
             B -> C

What's more, all the local variables and arguments of the first call to B are clobbered when the second call to B occurs.