That was the point. Most of the other students in the class were CS majors, and so had that point already drilled thoroughly into their heads, and were amazed that I could give such an ignorant answer. But since I was an astronomy major, it hadn’t been drilled into my head, so I honestly wasn’t sure.
Oh, I totally misread that. I thought you said that you said something along the lines of “it depends whether it uses a for loop or recursion” and the students were dumbfounded that they were different in overhead.
While there may be some implementations of F77 which support recursion, the language standard says it doesn’t.
The FORTRAN 77 standard was written by a committee, in a process we call camel-ing. Some number of people voted for the language without defining what they meant.
The point I’m making is that recursion is an algorithmic construct, not an implementation one. Statements like that in a standard tend to cloud the issue. How the stack is maintained and where local data is stored isn’t really relevant to the algorithm. For instance in older versions of FORTRAN, there was a static allocation of memory for the return address of each subroutine in the source code. So no subroutine could be re-entered at a different stack level, whether or not the purpose was recursion. Your subroutine would return to the last address it was called from, not to an address maintained on a stack. But you can implement your own stack as data, and recursive algorithms can be implemented in a simple loop without any subroutine calls. Older versions of FORTRAN did lots of stupid things in some implementations. It was common for people to redefine the value of constants in a program by passing them as parameters because compilers defined the constants as a memory location to simplify the compiler.
I think the line has to be drawn earlier than this. Saying you can implement recursive algorithm in F77 is not a lot different to saying that you can implement almost any language feature. Yes you can do it. But when the language specifically prohibited rentrant function calls I think we can take the position that F77 itself did not provide recursion. Otherwise once the language is sufficiently complete (which for all useful intents most are) you can argue that all languages provide all features. Provision of a feature is not the same as not prohibiting a feature. F77 didn’t prohibit you from writing a recursive algorithm. It did not provide support for writing a recursive algorithm.
That’s a good way of putting it.
To get technical about it (and why not?) this is called ‘Turing equivalence’; all that is required to be Turing equivalent is a conditional branch statement (if x then goto A), the ability to modify arbitrary memory locations (theoretically you need to always have ‘enough’ memory, which is not the case in reality), and an explicit HALT statement.
You can implement any Turing equivalent language in terms of any other, and compute any Turing complete function in any Turing equivalent language. (In theory. In practice, you might run up against stupid arbitrary limits, like the fact IBM 1401 assembly language only runs on systems with too little storage to really implement something capable of playing Quake 3.) A lot of languages are Turing equivalent, even ones that perhaps shouldn’t be.
Here’s a good take on this subject; the author of that post also wrote about other pathological programming languages.
After trying to get my head around recursion for the last 24hrs, I was relived to find your post and so created an account here just so I could say, thank you for taking the time to answer the question and explain this so clearly. God bless.