Какие императивные языки программирования не поддерживают рекурсию?

21

Насколько мне известно, все современные императивные языки программирования поддерживают рекурсию в том смысле, что процедура может вызывать сама себя. Это не всегда имело место, но я не могу найти какие-либо веские факты с помощью быстрого поиска в Google. Итак, мой вопрос:

Какие языки не поддерживали рекурсию с самого начала и когда эта поддержка была добавлена?

fredoverflow
источник

Ответы:

21

Я не уверен, что это делает COBOL (это точно не было когда-то), но я не могу даже вообразить, что кому-то это небезразлично.

Fortran существует с Fortran 90, но требует, чтобы вы использовали recursiveключевое слово, чтобы сказать ему, что подпрограмма рекурсивна.

PL / I был почти таким же - рекурсия поддерживалась, но вы должны были явно указать ей, какие процедуры были рекурсивными.

Я сомневаюсь, что есть намного больше чем это все же. Когда вы дойдете до этого, запрет рекурсии был в основном тем, что IBM сделала в своих языковых разработках по той простой причине, что мэйнфреймы IBM (360/370/3090 / ...) не поддерживают аппаратный стек. Когда большинство языков пришло от IBM, они в основном запрещали рекурсию. Теперь, когда все они приходят из других мест, рекурсия всегда разрешена (хотя я должен добавить, что несколько других машин, особенно оригинальный Cray 1, также не имели аппаратной поддержки стека).

Джерри Гроб
источник
Компьютеры контрольных данных того периода также не поддерживали рекурсию (вызовы подпрограмм выполнялись с помощью инструкции, которая изменила код для вставки перехода к инструкции вызова + 1). Когда Вирт разработал Паскаль на 6600, он, вероятно, должен был придумать новый способ вызова подпрограмм.
Дэвид Торнли
@ Дэвид: да - и не случайно, они были также разработаны Сеймур Крей. Однажды мне пришлось взглянуть на компилятор Pascal 6000, но я не помню, чтобы смотрел на то, что он делал для генерации (симуляции?) Стековых фреймов.
Джерри Гроб
notably the original cray 1Итак, вам не нужна рекурсия для клонирования динозавров? Я полагаю, что на самом деле мы, обезьяны, должны качаться сквозь деревья.
normanthesquid
2
даже CAML (и OCAML, F #) нуждаются в явно отмеченных рекурсивных функциях.
JK.
1
@Panzercrisis: Я не уверен, что IBM участвовала в x86, но их текущие мейнфреймы прослеживаются непосредственно до IBM 360, появившегося на рынке в 1964 году, поэтому базовый дизайн предшествует x86 примерно на пару десятилетий.
Джерри Коффин
16

Википедия говорит:

Ранние языки, такие как Fortran, изначально не поддерживали рекурсию, потому что переменные были статически распределены, а также место для адреса возврата.

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

FORTRAN 77 не допускает рекурсии, Fortran 90 делает (рекурсивные процедуры должны быть явно объявлены так).

Большинство компиляторов FORTRAN 77 допускают рекурсию, некоторые (например, DEC) требуют использования опции компилятора (см. Главу «Опции компилятора»). GNU g77, который строго соответствует стандарту Fortran 77, вообще не допускает рекурсии.

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

Роберт Харви
источник
В iirc был, по крайней мере, один компилятор FORTRAN 77, который хотя и технически поддерживал рекурсию, но общее количество кадров стека, которое вы могли иметь, было настолько малым, рекурсия не могла эффективно использоваться для многих задач
jk.
6

Язык программирования OpenCL не поддерживает рекурсию. (см. раздел 6.8 спецификации OpenCL )

В настоящее время мотивация заключается в том, чтобы: а) нехватка места для глубоких стеков; б) желание статически знать общее требуемое распределение, чтобы оптимизировать производительность при наличии больших наборов регистров и обширного встраивания.

Это вполне может относиться к другим языкам программирования GPU, например, к шейдерным языкам.

grrussel
источник
2

Некоторые компиляторы c для небольших микроконтроллеров не поддерживают рекурсию, предположительно потому, что они имеют чрезвычайно ограниченный размер стека.

Жанна Пиндар
источник
Некоторые из этих микроконтроллеров (например, семейство PIC16) имеют только аппаратный стек вызовов (недоступный инструкциям) и не имеют какой-либо другой формы стека, поэтому функции не могут иметь локальные переменные при использовании рекурсии (поскольку стек данных явно необходим для этого ...) Ссылка: en.wikipedia.org/wiki/PIC_microcontroller#Stacks
Ale
1

BASIC, во времена номеров строк, имел тенденцию иметь плохую поддержку рекурсии. Многие (все?) ОСНОВЫ того времени поддерживали вложенные вызовы gosub, но не поддерживали простой способ передачи параметров или возвращаемых значений таким образом, чтобы сделать его полезным для самостоятельного вызова.

У многих ранних компьютеров были проблемы с рекурсией, потому что они использовали инструкции вызова, которые записывали адрес возврата в начало подпрограммы (PDP8, семейство компьютеров IAS, вероятно, больше архитектур, с которыми я не знаком), обычно таким образом, что это был машинный код для «Перейти к инструкции после той, которая вызывала подпрограмму».

Vatine
источник
1

Это зависит от того, что вы подразумеваете под « поддержкой ». Для поддержки рекурсии вам нужен стек, в котором для каждого повторного входа необходимо создавать экземпляры локальных переменных.

Даже если в языке нет понятия локальных переменных, если в нем есть понятие «подпрограмма» и есть способ управлять индексированием между одинаковыми переменными (иначе говоря, массивом), вы можете увеличивать / уменьшать глобальный индекс при каждом входе / выходе функции и доступ через нее к члену одного или нескольких массивов.

Я не знаю, можно ли это назвать «поддержкой». Факты в том, что я написал рекурсивную функцию с помощью ZX-Spectrum BASIC, как я делал это в Fortran77, как в COBOL ... всегда с этим трюком.

Эмилио Гаравалья
источник
1

Язык ассемблера напрямую не поддерживает рекурсию - вы должны «сделать это сами», обычно путем помещения параметров в стек компьютера.

mikera
источник
2
Он поддерживает рекурсию, поскольку поддерживает вызовы методов. Обычно есть CALLинструкция, которая автоматически помещает IP-адрес в стек перед переходом к подпрограмме, и RETинструкция, которая вставляет адрес возврата в IP-адрес. Нет причин, по которым ты не можешь открыть CALLсвою собственную точку входа.
Blorgbeard
@Blorgbeard - абсолютно верно, хотя я бы сказал, что этого недостаточно, чтобы считать «поддерживает рекурсию» в общепринятом смысле, поскольку он не обрабатывает параметры, необходимые для рекурсивного вызова.
Микера
1
Ну, рекурсивные вызовы технически не нуждаются в параметрах, верно? void f() { f(); }является рекурсивным
Blorgbeard
Технически нет. Но способность кодировать один тривиальный случай НЕ ИМХО не означает, что вы должны описать сборку как «поддерживающую рекурсию». Большинство практических применений рекурсии требуют параметров.
Микера
Я полагаю, вы могли бы сказать это. Но в этом случае сборка также не поддерживает циклы (вы должны вручную CMP и JNZ). Я думаю, это вопрос того, что вы называете "поддержкой".
Blorgbeard