O ile mi wiadomo, wszystkie współczesne imperatywne języki programowania obsługują rekurencję w tym sensie, że procedura może się nazywać sama. Nie zawsze tak było, ale nie mogę znaleźć żadnych twardych faktów dzięki szybkiemu wyszukiwaniu w Google. Więc moje pytanie brzmi:
Które języki od samego początku nie obsługiwały rekurencji i kiedy dodano tę obsługę?
Odpowiedzi:
Nie jestem pewien, czy COBOL tak robi (z pewnością tak nie było kiedyś), ale nie mogę sobie wyobrazić nikogo, kto by się tak bardzo przejmował.
Fortran ma od Fortran 90, ale wymaga użycia recursivesłowa kluczowego, aby powiedzieć, że podprogram jest rekurencyjny.
PL / I byłem prawie taki sam - rekurencja była obsługiwana, ale trzeba było wyraźnie powiedzieć, jakie procedury były rekurencyjne.
Wątpię jednak, aby było ich o wiele więcej. Kiedy do tego doszło, zakaz rekurencji był głównie czymś, co IBM zrobił w swoich projektach językowych, z tego prostego powodu, że komputery mainframe IBM (360/370/3090 / ...) nie obsługują stosu sprzętu. Kiedy większość języków pochodziła od IBM, najczęściej zabraniały rekursji. Teraz, gdy wszystkie pochodzą z innych miejsc, rekursja jest zawsze dozwolona (chociaż powinienem dodać, że kilka innych maszyn, zwłaszcza oryginalny Cray 1, również nie miało obsługi sprzętowej dla stosu).
notably the original cray 1Więc nie potrzebujesz rekurencji, aby sklonować dinozaury? Wydaje mi się, że to naprawdę do nas, małp, należy huśtać się między drzewami.
Wikipedia mówi:
Wczesne języki, takie jak Fortran, początkowo nie obsługiwały rekurencji, ponieważ zmienne były przydzielane statycznie, a także lokalizacja adresu zwrotnego.
http://en.wikipedia.org/wiki/Subroutine#Local_variables.2C_recursion_and_re-entrancy
FORTRAN 77 nie pozwala na rekurencję, Fortran 90 tak, (procedury rekurencyjne muszą być wyraźnie zadeklarowane).
Większość kompilatorów FORTRAN 77 umożliwia rekurencję, niektóre (np. DEC) wymagają użycia opcji kompilatora (patrz rozdział opcji kompilatora). GNU g77, który jest ściśle zgodny ze standardem Fortran 77, w ogóle nie pozwala na rekurencję.
Język programowania OpenCL nie obsługuje rekurencji. (patrz sekcja 6.8 specyfikacji OpenCL )
Obecną motywacją tego jest a) brak miejsca na głębokie stosy b) chęć poznania, statycznie, całkowitych wymaganych przydziałów w celu zoptymalizowania wydajności w obecności dużych zestawów rejestrów i obszernego wbudowania.
Może to również dotyczyć innych języków programowania GPU, np. Języków shaderów.
Niektóre kompilatory c dla małych mikrokontrolerów nie obsługują rekurencji, prawdopodobnie dlatego, że mają bardzo ograniczony rozmiar stosu.
BASIC, w czasach numerów linii, zwykle słabo obsługiwał rekurencję. Wiele (wszystkich?) BASIC ówczesnych obsługiwało zagnieżdżone wywołania gosub, ale nie obsługiwało łatwego sposobu przekazywania parametrów lub zwracania wartości w sposób, który czyniłby użyteczne samodzielne wywołanie.
Wiele wczesnych komputerów miało problemy z rekurencją, ponieważ korzystały z instrukcji wywołania, które zapisały adres zwrotny na początku procedury o nazwie (PDP8, rodzina maszyn IAS, prawdopodobnie więcej architektur, których nie znam), zwykle w taki sposób, że był kod maszynowy dla „Przejdź do instrukcji po tej, która wywołała procedurę”.
To zależy od tego, co rozumiesz przez „ wsparcie ”. Do obsługi rekurencji potrzebny jest stos, w którym przy każdym ponownym wejściu należy ponownie tworzyć zmienne lokalne.
Nawet jeśli język nie ma pojęcia zmiennych lokalnych, jeśli ma pojęcie „podprogramu” i ma sposób zarządzania indeksowaniem między identycznymi zmiennymi (inaczej tablicą), możesz zwiększać / zmniejszać indeks globalny przy każdym wejściu / wyjściu funkcji i dostęp do niej przez członka jednej lub więcej tablic.
Nie wiem, czy można to nazwać „wsparciem”. Fakty są takie, że napisałem funkcję rekurencyjną w ZX-Spectrum BASIC, tak jak to zrobiłem w Fortran77 jak w COBOL ... zawsze z tą sztuczką.
Język asemblera nie obsługuje bezpośrednio rekurencji - musisz „zrób to sam”, zwykle poprzez wypchnięcie parametrów na stos maszyny.
CALLinstrukcja, która automatycznie wypycha adres IP na stos przed przejściem do podprogramu, oraz instrukcja, która wstawia RETadres zwrotny do adresu IP. Nie ma powodu, dla którego nie możesz mieć CALLwłasnego punktu wejścia.
void f() { f(); }jest rekurencyjny.