Talk:Non-structured programming

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.


As I just wrote in an edit, general recursion in non-structured programs is not possible, i.e. a subroutine cannot call itself at an arbitrary point and then take the return value of that call and proceed with what it was doing, assuming that its own state (values of variables) after the call will be consistent with its state before the call. However, recursion is possible in a non-structured program in limited cases—namely, cases where no values of variables which represent the state of the subroutine are needed after the recursive call. The most obvious case of this is tail-call recursion, but it also includes subroutine structures where the recursive call is not strictly a tail-call but where only constants and the return value of a recursive call are used for computation after the recursive call. In some cases, a recursive subroutine that uses state variables after a recursive call can be reformulated as one that does not.

Other than the tail-call or near tail-call strategy, it is always possible to preserve a subroutine's state through recursive calls by explicitly implementing an effective stack in a dedicated global variable. E.g., a subroutine in a non-structured language has a global variable for an input parameter (since all variables in the language are global), a global variable for an output parameter, and a global variable or variables implementing a stack, perhaps as an array of bytes and a top-of-stack index pointer variable. When the subroutine makes a recursive call, it "pushes" its later-needed state variables onto its self-fashioned stack, and after the call, it "pops" the same variables back off, all using explicit manipulation of the stack variables or explicitly written subroutines that do the same. The subroutine could even use the stack array as its local variables, setting up a frame on the stack when it starts and tearing it down before it returns. This is all very similar to assembly language programming in principle, but it works.

So, in conclusion, limited recursion is possible in non-structured languages natively (to infinite depth, with tail-call optimization), while unlimited recursion is possible if the non-structured language is augmented with a stack implemented explicitly in the language. This obviously must be true, since all high level languages that support general recursion are ultimately implemented in machine languages which are completely unstructured. (talk) 16:08, 3 October 2009 (UTC)