Quais linguagens de programação imperativas não suportam recursão?

21

Que eu saiba, todas as linguagens de programação imperativas modernas suportam recursão no sentido em que um procedimento pode se chamar. Nem sempre foi esse o caso, mas não consigo encontrar fatos concretos com uma rápida pesquisa no Google. Então, minha pergunta é:

Quais idiomas não suportaram recursão desde o início e quando esse suporte foi adicionado?

fredoverflow
fonte

Respostas:

21

Não sei se o COBOL funciona (certamente não funcionou ao mesmo tempo), mas também não consigo imaginar alguém se importando muito.

O Fortran possui desde o Fortran 90, mas exige que você use a recursivepalavra-chave para informar que uma sub-rotina é recursiva.

O PL / I era praticamente o mesmo - a recursão era suportada, mas você precisava explicitamente dizer quais procedimentos eram recursivos.

Duvido que haja muito mais que isso. Quando se trata disso, proibir a recursão era principalmente algo que a IBM fazia em seus designs de idiomas, pelo simples motivo de que os mainframes da IBM (360/370/3090 / ...) não suportam uma pilha de hardware. Quando a maioria dos idiomas veio da IBM, eles proibiram a recursão. Agora que todos eles vêm de outros lugares, a recursão é sempre permitida (embora eu deva acrescentar que algumas outras máquinas, principalmente a Cray 1 original, também não tinham suporte de hardware para uma pilha).

Jerry Coffin
fonte
Os computadores dos Dados de Controle do período também não suportaram recursão (as chamadas de sub-rotina foram feitas com uma instrução que modificou o código para inserir um salto na instrução de chamada + 1). Quando Wirth desenvolveu Pascal no 6600, ele provavelmente teve que inventar uma nova maneira de chamar sub-rotinas.
precisa
@ David: sim - e sem coincidência, eles também foram projetados por Seymour Cray. Uma vez cheguei a olhar para o compilador Pascal 6000, mas não me lembro de ter examinado o que ele fez para gerar (simular?) Quadros de pilha.
Jerry Coffin
notably the original cray 1Então, você não precisa de recursão para clonar dinossauros? Acho que depende de nós, macacos, passar por entre as árvores.
Normanthesquid
2
até CAML (e OCAML, F #) precisam de funções recursivas marcadas explicitamente.
jk.
1
@ Panzercrisis: Não tenho certeza se a IBM estava envolvida no x86, mas seus mainframes atuais remontam diretamente ao IBM 360, que foi lançado no mercado em 1964, então o design básico antecede o x86 em algumas décadas.
Jerry Coffin
16

A Wikipedia diz:

Idiomas antigos, como o Fortran, inicialmente não suportavam recursão porque as variáveis ​​eram alocadas estaticamente, assim como o local do endereço de retorno.

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

FORTRAN 77 não permite recursão, Fortran 90, (rotinas recursivas devem ser explicitamente declaradas).

A maioria dos compiladores FORTRAN 77 permite recursão, alguns (por exemplo, DEC) requerem o uso de uma opção de compilador (consulte o capítulo de opções do compilador). O GNU g77, que está em conformidade estritamente com o padrão Fortran 77, não permite recursão.

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

Robert Harvey
fonte
iirc, havia pelo menos um compilador FORTRAN 77 que, embora tecnicamente suportasse recursão, o número total de quadros de pilha que você poderia ter era tão pequeno que a recursão não era efetivamente utilizável para muitos problemas
jk.
6

A linguagem de programação OpenCL não suporta recursão. (consulte a seção 6.8 das especificações do OpenCL )

A motivação atual para isso é: a) falta de espaço para pilhas profundas; b) desejo de saber, estaticamente, o total de alocações necessárias para otimizar o desempenho na presença de grandes conjuntos de registros e amplo alinhamento.

Isso pode se aplicar a outras linguagens de programação da GPU, por exemplo, linguagens de sombreador.

Grrussel
fonte
2

Alguns compiladores c para microcontroladores pequenos não suportam recursão, provavelmente porque eles têm um tamanho de pilha extremamente limitado.

Jeanne Pindar
fonte
Alguns desses microcontroladores (por exemplo, família PIC16) possuem apenas uma pilha de chamadas de hardware (não acessível por instruções) e nenhuma outra forma de pilha; portanto, as funções não podem ter variáveis ​​locais ao usar a recursão (pois é claramente necessária uma pilha de dados para isso ...) Referência: en.wikipedia.org/wiki/PIC_microcontroller#Stacks
Ale
1

O BASIC, nos dias de números de linha, tendia a ter um suporte insuficiente à recursão. Muitos BASICs (todos?) Da época eram compatíveis com chamadas aninhadas ao gosub, mas não suportavam uma maneira fácil de passar parâmetros ou retornar valores de uma maneira que tornava útil a auto-chamada.

Muitos computadores antigos tiveram problemas com a recursão, porque usaram instruções de chamada que escreveram o endereço de retorno no início da rotina chamada (PDP8, a família de máquinas IAS, provavelmente mais arquiteturas com as quais não estou familiarizado), geralmente de tal maneira que era o código de máquina para "Salte para a instrução após a que chamou a rotina".

Vatine
fonte
1

Depende do que você quer dizer com " suporte ". Para dar suporte à recursão, você precisa de uma pilha onde re-instanciar variáveis ​​locais a cada reentrada.

Mesmo se o idioma não tiver o conceito de variáveis ​​locais, se ele tiver o conceito de "sub-rotina" e tiver uma maneira de gerenciar uma indexação entre variáveis ​​idênticas (aka matriz), você poderá aumentar / diminuir um índice global a cada entrada / saída de uma função e acesse através dela um membro de uma ou mais matrizes.

Não sei se isso pode ser chamado de "suporte". Os fatos são que escrevi função recursiva com o ZX-Spectrum BASIC, como fiz no Fortran77 e no COBOL ... sempre com esse truque.

Emilio Garavaglia
fonte
1

A linguagem assembly não suporta diretamente a recursão - você precisa "fazer você mesmo", normalmente pressionando parâmetros na pilha da máquina.

Mikera
fonte
2
Ele suporta recursão na medida em que suporta chamadas de método. Geralmente, há uma CALLinstrução que empurra o IP automaticamente para a pilha antes de pular para a sub-rotina e uma RETinstrução que insere o endereço de retorno no IP. Não há motivo para você não ter CALLseu próprio ponto de entrada.
Blorgbeard
@ Blorgbeard - absolutamente verdade, embora eu argumentasse que isso é insuficiente para contar como "suporta recursão" no sentido comumente entendido, pois não lida com os parâmetros necessários para a chamada recursiva.
Mikera
1
Bem, chamadas recursivas tecnicamente não precisam de parâmetros, certo? void f() { f(); }é recursivo.
Blorgbeard
Tecnicamente, não. Mas ser capaz de codificar um caso trivial não significa que você deve descrever o assembly como "recursão de suporte". Os usos mais práticos da recursão requerem parâmetros.
Mikera
Suponho que você possa dizer isso. Mas, nesse caso, a montagem também não suporta loops (você precisa manualmente CMP e JNZ). Eu acho que é uma questão do que você chama de "apoio".
Blorgbeard