24

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?

fredoverflow
  • 6,854
  • 8
  • 39
  • 46

7 Answers7

24

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).

Jerry Coffin
  • 44,385
  • 5
  • 89
  • 162
  • 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 05 '11 at 14:05
  • Cray 1 didn't have support for stack?! Live and learn. – Secko Aug 01 '12 at 02:09
  • 3
    even CAML (and OCAML, F#) need recursive functions explicit marked. – jk. Aug 01 '12 at 07:15
  • 1
    PASCAL 6000 maintained a software stack, manually pushing and popping arguments and return addresses. To call a routine, code pushed the return address onto the stack and then executed an unconditional branch. To return, code in the subroutine popped the return address, moved it into a B-register (index register) and executed a JP Bn to jump to the address in the specified B-register. – John R. Strohm Aug 01 '12 at 14:02
  • It's surprising IBM machines wouldn't have a stack. Wasn't IBM involved with the x86 architecture? If they were, then I guess they made an improvement in that case. – Panzercrisis Sep 05 '14 at 03:45
  • 1
    @Panzercrisis: I'm not sure whether IBM was involved in the x86, but their current mainframes trace directly back to the IBM 360, which came on the market in 1964, so the basic design predates the x86 by a couple decades or so. – Jerry Coffin Sep 05 '14 at 15:07
  • 1
    In Fortran 2018 recursive procedures are the default and a new NON_RECURSIVE keyword was added. – Vladimir F Героям слава Mar 19 '18 at 14:42
19

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

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
  • 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 06 '11 at 08:58
8

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.

grrussel
  • 469
  • 3
  • 5
2

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

Jeanne Pindar
  • 126
  • 1
  • 7
  • Some of those microcontrollers (e.g. PIC16 family) only have a hardware call stack (not accessible by instructions) and don't have any other form of stack, so functions could not have local variables when using recursion (as a data stack is clearly needed for that...) Reference: https://en.wikipedia.org/wiki/PIC_microcontroller#Stacks – Ale Jul 29 '17 at 20:30
1

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".

Vatine
  • 4,251
  • 21
  • 20
1

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.

Emilio Garavaglia
  • 4,289
  • 1
  • 22
  • 23
1

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

mikera
  • 20,617
  • 5
  • 75
  • 80
  • 2
    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 01 '12 at 04: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 01 '12 at 04:51
  • 1
    Well, recursive calls don't technically need parameters, right? `void f() { f(); }` is recursive. – Blorgbeard Aug 01 '12 at 04: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 01 '12 at 05: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 01 '12 at 20:36