Welche imperativen Programmiersprachen unterstützen keine Rekursion?

21

Meines Wissens unterstützen alle modernen imperativen Programmiersprachen die Rekursion in dem Sinne, dass eine Prozedur sich selbst aufrufen kann. Dies war nicht immer der Fall, aber ich kann mit einer schnellen Google-Suche keine harten Fakten finden. Meine Frage lautet also:

Welche Sprachen haben Rekursion von Anfang an nicht unterstützt und wann wurde diese Unterstützung hinzugefügt?

fredoverflow
quelle

Antworten:

21

Ich bin mir nicht sicher, ob COBOL das tut (das hat es auf jeden Fall nicht einmal getan), aber ich kann mir auch nicht vorstellen, dass sich jemand viel für mich interessiert.

Fortran gibt es seit Fortran 90, aber Sie müssen das recursiveSchlüsselwort verwenden, um anzugeben, dass eine Subroutine rekursiv ist.

PL / I war so ziemlich dasselbe - Rekursion wurde unterstützt, aber Sie mussten explizit angeben, welche Prozeduren rekursiv waren.

Ich bezweifle, dass es noch viel mehr gibt. Das Verbot der Rekursion war in den meisten Fällen etwas, was IBM in seinen Sprachentwürfen getan hat, aus dem einfachen Grund, dass IBM-Mainframes (360/370/3090 / ...) keinen Stack in Hardware unterstützen. Wenn die meisten Sprachen von IBM stammen, ist die Rekursion meistens verboten. Jetzt, da sie alle von anderen Orten stammen, ist Rekursion immer erlaubt (obwohl ich hinzufügen sollte, dass einige andere Maschinen, insbesondere die ursprüngliche Cray 1, auch keine Hardware-Unterstützung für einen Stack hatten).

Jerry Sarg
quelle
Control Data-Computer der Periode unterstützten ebenfalls keine Rekursion (Unterprogrammaufrufe wurden mit einer Anweisung durchgeführt, die den Code so änderte, dass ein Sprung zur aufrufenden Anweisung + 1 eingefügt wurde). Als Wirth Pascal auf der 6600 entwickelte, musste er sich vermutlich eine neue Methode einfallen lassen, um Unterprogramme aufzurufen.
David Thornley
@ David: Ja - und kein Zufall, sie wurden auch von Seymour Cray entworfen. Ich habe mir einmal den Pascal 6000-Compiler angesehen, kann mich aber nicht erinnern, dass ich mir angesehen habe, wie er Stapelrahmen erzeugt (simuliert?) Hat.
Jerry Coffin
notably the original cray 1Sie brauchen also keine Rekursion, um Dinosaurier zu klonen? Ich denke, es liegt wirklich an uns Affen, durch die Bäume zu schwingen.
Normanthesquid
2
Selbst CAML (und OCAML, F #) benötigen explizit markierte rekursive Funktionen.
jk.
1
@Panzercrisis: Ich bin mir nicht sicher, ob IBM an x86 beteiligt war, aber die aktuellen Mainframes gehen direkt auf die IBM 360 zurück, die 1964 auf den Markt kam.
Jerry Coffin
16

Wikipedia sagt:

Frühe Sprachen wie Fortran unterstützten die Rekursion anfangs nicht, da Variablen statisch zugeordnet wurden und auch der Speicherort für die Absenderadresse.

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

FORTRAN 77 lässt keine Rekursion zu, Fortran 90 hingegen (rekursive Routinen müssen explizit deklariert werden).

Die meisten FORTRAN 77-Compiler erlauben eine Rekursion, einige (z. B. DEC) erfordern die Verwendung einer Compiler-Option (siehe Kapitel Compiler-Optionen). Die GNU g77, die sich strikt an den Fortran 77-Standard hält, erlaubt überhaupt keine Rekursion.

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

Robert Harvey
quelle
Es gab mindestens einen FORTRAN 77-Compiler, der die Rekursion zwar technisch unterstützte, die Gesamtzahl der Stack-Frames, die Sie haben konnten, jedoch so gering war, dass die Rekursion für viele Probleme nicht effektiv nutzbar war
jk.
6

Die OpenCL-Programmiersprache unterstützt keine Rekursion. (siehe Abschnitt 6.8 der OpenCL-Spezifikation )

Die gegenwärtige Motivation dafür ist a) ein Mangel an Platz für tiefe Stapel, b) der Wunsch, statisch die insgesamt erforderlichen Zuweisungen zu kennen, um die Leistung bei Vorhandensein großer Registersätze und umfangreicher Einlagerung zu optimieren.

Dies gilt möglicherweise auch für andere GPU-Programmiersprachen, z. B. Shader-Sprachen.

grrussel
quelle
2

Einige c-Compiler für kleine Mikrocontroller unterstützen keine Rekursion, vermutlich weil sie eine extrem begrenzte Stapelgröße haben.

Jeanne Pindar
quelle
Einige dieser Mikrocontroller (z. B. die PIC16-Familie) verfügen nur über einen Hardware-Aufrufstapel (auf den nicht durch Anweisungen zugegriffen werden kann) und haben keine andere Form des Stapels. Daher können Funktionen bei Verwendung der Rekursion keine lokalen Variablen aufweisen (da ein Datenstapel eindeutig benötigt wird) dafür ...) Referenz: en.wikipedia.org/wiki/PIC_microcontroller#Stacks
Ale
1

In den Tagen der Zeilennummern hatte BASIC eine schlechte Rekursionsunterstützung. Viele (alle?) BASICs dieser Zeit unterstützten verschachtelte gosub-Aufrufe, aber nicht die einfache Übergabe von Parametern oder Rückgabewerten in einer Weise, die es nützlich machte, sich selbst aufzurufen.

Viele frühe Computer hatten Probleme mit der Rekursion, weil sie Aufrufanweisungen verwendeten, die die Rücksprungadresse in den Anfang der aufgerufenen Routine schrieben (PDP8, die IAS-Maschinenfamilie, wahrscheinlich mehr Architekturen, mit denen ich nicht vertraut bin), normalerweise so, dass dies der Fall war war der Maschinencode für "Sprung zur Anweisung nach derjenigen, die die Routine aufgerufen hat".

Vatine
quelle
1

Es kommt darauf an, was Sie unter " Unterstützung " verstehen . Um die Rekursion zu unterstützen, benötigen Sie einen Stapel, in dem lokale Variablen bei jedem Wiedereintritt erneut instanziiert werden.

Auch wenn die Sprache nicht über das Konzept lokaler Variablen verfügt, können Sie bei jeder Eingabe / Ausgabe einen globalen Index inkrementieren / dekrementieren, wenn sie über das Konzept der "Unterroutine" verfügt und eine Möglichkeit zum Verwalten der Indizierung zwischen identischen Variablen (auch als Array bezeichnet) bietet einer Funktion und greifen dadurch auf ein Mitglied eines oder mehrerer Arrays zu.

Ich weiß nicht, ob dies als "Support" bezeichnet werden kann. Die Fakten sind, dass ich rekursive Funktionen mit dem ZX-Spectrum BASIC geschrieben habe, wie ich es in Fortran77 und in COBOL getan habe ... immer mit diesem Trick.

Emilio Garavaglia
quelle
1

Die Assembler-Sprache unterstützt Rekursion nicht direkt - Sie müssen es selbst tun, indem Sie normalerweise Parameter auf den Maschinenstapel übertragen.

mikera
quelle
2
Es unterstützt die Rekursion, sofern es Methodenaufrufe unterstützt. Normalerweise gibt es eineCALL Anweisung, die die IP- RETAdresse automatisch auf den Stapel schiebt, bevor zur Unterroutine gesprungen wird, und eine Anweisung, die die Rücksprungadresse in die IP-Adresse einfügt. Es gibt keinen Grund, warum Sie nicht CALLIhren eigenen Einstiegspunkt haben können.
Blorgbeard
@Blorgbeard - absolut wahr, obwohl ich behaupten würde, dass dies nicht ausreicht, um als "Unterstützungsrekursion" im allgemein verständlichen Sinne zu gelten, da es nicht die für den rekursiven Aufruf erforderlichen Parameter verarbeitet.
mikera
1
Nun, rekursive Aufrufe benötigen technisch gesehen keine Parameter, oder? void f() { f(); }ist rekursiv.
Blorgbeard
Technisch nein. Aber in der Lage zu sein, einen einfachen Fall zu codieren, bedeutet IMHO nicht, dass Sie Assembly als "unterstützende Rekursion" bezeichnen sollten. Die meisten praktischen Verwendungen der Rekursion erfordern Parameter.
Mikera
Das könnte man wohl sagen. In diesem Fall unterstützt Assembly jedoch auch keine Schleifen (Sie müssen CMP und JNZ manuell ausführen). Ich denke, es ist eine Frage dessen, was Sie "unterstützen" nennen.
Blorgbeard