Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

To my knowledge, all modern imperative programming languages support recursion in the sense that a procedure can call itself. This was not always the case, but I cannot find any hard facts with a quick Google search. So my question is:

Which languages did not support recursion right from the start and when was that support added?

share|improve this question
add comment

7 Answers 7

up vote 18 down vote accepted

I'm not sure COBOL does (it certainly didn't at one time), but I can't quite imagine anybody caring much either.

Fortran has since Fortran 90, but requires that you use the recursive keyword to tell it that a subroutine is recursive.

PL/I was pretty much the same -- recursion was supported, but you had to explicitly tell it what procedures were recursive.

I doubt there are many more than that though. When you get down to it, prohibiting recursion was mostly something IBM did in their language designs, for the simple reason that IBM (360/370/3090/...) mainframes don't support a stack in hardware. When most languages came from IBM, they mostly prohibited recursion. Now that they all come from other places, recursion is always allowed (though I should add that a few other machines, notably the original Cray 1, didn't have hardware support for a stack either).

share|improve this answer
    
Control Data computers of the period didn't support recursion either (subroutine calls were done with an instruction that modified the code to insert a jump to the calling instruction + 1). When Wirth developed Pascal on the 6600, he presumably had to come up with a new way to call subroutines. –  David Thornley Nov 24 '10 at 22:46
    
@David: yes -- and no coincidence, they were also designed by Seymour Cray. I once got to look at the Pascal 6000 compiler, but don't recall having looked at what it did to generate (simulate?) stack frames. –  Jerry Coffin Nov 24 '10 at 22:56
    
notably the original cray 1 So, you don't need recursion to clone dinosaurs? I guess it really is up to us monkeys to swing through the trees. –  normanthesquid Oct 5 '11 at 14:05
    
Cray 1 didn't have support for stack?! Live and learn. –  Secko Aug 1 '12 at 2:09
1  
even CAML (and OCAML, F#) need recursive functions explicit marked. –  jk. Aug 1 '12 at 7:15
show 1 more comment

Wikipedia says:

Early languages like Fortran did not initially support recursion because variables were statically allocated, as well as the location for the return address.

http://en.wikipedia.org/wiki/Subroutine#Local_variables.2C_recursion_and_re-entrancy

FORTRAN 77 does not allow recursion, Fortran 90 does, (recursive routines must be explicitly declared so).

Most FORTRAN 77 compilers allow recursion, some (e.g. DEC) require using a compiler option (see compiler options chapter). The GNU g77, which conforms strictly to the Fortran 77 standard, doesn't allow recursion at all.

http://www.ibiblio.org/pub/languages/fortran/ch1-12.html

share|improve this answer
    
iirc there was at least one FORTRAN 77 compiler that, while it technically supported recursion, the total number of stack frames you could have were so small recursion was not effectively usable for many problems –  jk. Oct 6 '11 at 8:58
add comment

Some c compilers for small microcontrollers don't support recursion, presumably because they have an extremely limited stack size.

share|improve this answer
add comment

BASIC, in the days of line-numbers, tended to have poor recursion support. Many (all?) BASICs of that time supported nested gosub calls, but did not support an easy way of passing parameters or return values in a way that made it useful to self-call.

Many early computers had problems with recursion, because they used call instructions that wrote the return address into the beginning of the routine called (PDP8, the IAS family of machines, probably more architectures I am unfamiliar with), usually in such a way that it was the machine code for "Jump to the instruction after the one that called the routine".

share|improve this answer
add comment

The OpenCL programming language does not support recursion. (see section 6.8 of the OpenCL Spec)

The current motivation for that is a) a lack of space for deep stacks b) a desire to know, statically, the total required allocations in order to optimize for performance in the presence of large register sets and extensive in-lining.

This may well apply to other GPU programming languages, e.g. shader languages.

share|improve this answer
add comment

It depends on what you mean by "support". To support recursion you need a stack where to re-instantiate local variables at every re-entrance.

Even if the language does not have the concept of local variables, if it has the concept of "subroutine" and has a way to manage an indexing between identical variables (a.k.a. array) you can increment / decrement a global index upon every enter / exit of a function and access through it a member of one or more array.

I don't know if this can be called "support". The facts are that I wrote recursive function with the ZX-Spectrum BASIC, as I did it in Fortran77 as in COBOL ... always with that trick.

share|improve this answer
add comment

Assembly language doesn't directly support recursion - you have to "do it yourself", typically by pushing parameters onto the machine stack.

share|improve this answer
1  
It supports recursion as far as it supports method calls. There's usually a CALL instruction, which automatically pushes the IP to the stack before jumping to the subroutine, and a RET instructions which pops the return address into the IP. There's no reason you can't CALL your own entry-point. –  Blorgbeard Aug 1 '12 at 4:32
    
@Blorgbeard - absolutely true, although I'd argue that this is insufficient to count as "supports recursion" in the commonly understood sense as it doesn't handle the parameters needed for the recursive call. –  mikera Aug 1 '12 at 4:51
1  
Well, recursive calls don't technically need parameters, right? void f() { f(); } is recursive. –  Blorgbeard Aug 1 '12 at 4:58
    
Technically, no. But being able to code one trivial case doesn't IMHO mean that you should should describe assembly as "supporting recursion". Most practical uses of recursion require parameters. –  mikera Aug 1 '12 at 5:19
    
I suppose you could say that. But in that case, assembly also doesn't support loops (you have to manually CMP and JNZ). I guess it's a matter of what you call "supporting". –  Blorgbeard Aug 1 '12 at 20:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.