Quels langages de programmation impératifs ne prennent pas en charge la récursivité?

21

À ma connaissance, tous les langages de programmation impératifs modernes prennent en charge la récursivité dans le sens où une procédure peut s'appeler elle-même. Ce n'était pas toujours le cas, mais je ne trouve aucun fait concret avec une recherche rapide sur Google. Ma question est donc:

Quelles langues n'ont pas pris en charge la récursivité dès le départ et quand ce support a-t-il été ajouté?

programming-languages recursion fredoverflow
la source

Réponses:

21

Je ne suis pas sûr que COBOL le fasse (certainement pas à un moment donné), mais je ne peux pas imaginer que quiconque se soucie beaucoup non plus.

Fortran a depuis Fortran 90, mais vous oblige à utiliser le recursivemot - clé pour lui dire qu'un sous-programme est récursif.

PL / I était à peu près la même - la récursivité était prise en charge, mais vous deviez lui dire explicitement quelles procédures étaient récursives.

Je doute qu'il y en ait bien plus que cela. Quand vous y arrivez, interdire la récursivité était principalement quelque chose qu'IBM a fait dans ses conceptions de langage, pour la simple raison que les mainframes IBM (360/370/3090 / ...) ne prennent pas en charge une pile matérielle. Lorsque la plupart des langues provenaient d'IBM, elles interdisaient principalement la récursivité. Maintenant qu'ils viennent tous d'autres endroits, la récursivité est toujours autorisée (même si je dois ajouter que quelques autres machines, notamment le Cray 1 d'origine, n'avaient pas non plus de support matériel pour une pile).

Jerry Coffin
la source
Les ordinateurs de données de contrôle de la période ne prenaient pas non plus en charge la récursivité (les appels de sous-programme ont été effectués avec une instruction qui a modifié le code pour insérer un saut dans l'instruction appelante + 1). Lorsque Wirth a développé Pascal sur le 6600, il a probablement dû trouver une nouvelle façon d'appeler les sous-programmes.
David Thornley
@David: oui - et pas une coïncidence, ils ont également été conçus par Seymour Cray. Une fois, j'ai pu regarder le compilateur Pascal 6000, mais je ne me souviens pas avoir regardé ce qu'il a fait pour générer (simuler?) Des cadres de pile.
Jerry Coffin
notably the original cray 1Donc, vous n'avez pas besoin de récursivité pour cloner des dinosaures? Je suppose que c'est vraiment à nous les singes de se balancer dans les arbres.
normanthesquid
2
même CAML (et OCAML, F #) ont besoin de fonctions récursives explicitement marquées.
jk.
1
@Panzercrisis: Je ne sais pas si IBM était impliqué dans le x86, mais leurs mainframes actuels remontent directement à l'IBM 360, qui est arrivé sur le marché en 1964, donc la conception de base est antérieure au x86 de quelques décennies.
Jerry Coffin du
16

Wikipédia dit:

Les premières langues comme Fortran ne prenaient pas initialement en charge la récursivité car les variables étaient allouées statiquement, ainsi que l'emplacement de l'adresse de retour.

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

FORTRAN 77 ne permet pas la récursivité, Fortran 90 le permet (les routines récursives doivent être explicitement déclarées ainsi).

La plupart des compilateurs FORTRAN 77 autorisent la récursivité, certains (par exemple DEC) nécessitent l'utilisation d'une option de compilation (voir le chapitre des options de compilation). Le GNU g77, qui se conforme strictement à la norme Fortran 77, ne permet pas du tout la récursivité.

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

Robert Harvey
la source
iirc il y avait au moins un compilateur FORTRAN 77 qui, bien qu'il supportait techniquement la récursivité, le nombre total de trames de pile que vous pouviez avoir était si petite récursivité n'était pas effectivement utilisable pour de nombreux problèmes
jk.
6

Le langage de programmation OpenCL ne prend pas en charge la récursivité. (voir la section 6.8 de la spécification OpenCL )

La motivation actuelle pour cela est a) un manque d'espace pour les piles profondes b) un désir de connaître, statiquement, les allocations totales requises afin d'optimiser les performances en présence de grands ensembles de registres et d'un alignement étendu.

Cela peut s'appliquer à d'autres langages de programmation GPU, par exemple les langages de shader.

grrussel
la source
2

Certains compilateurs c pour les petits microcontrôleurs ne prennent pas en charge la récursivité, probablement parce qu'ils ont une taille de pile extrêmement limitée.

Jeanne Pindar
la source
Certains de ces microcontrôleurs (par exemple la famille PIC16) n'ont qu'une pile d'appels matériels (non accessible par des instructions) et n'ont pas d'autre forme de pile, donc les fonctions ne pouvaient pas avoir de variables locales lors de l'utilisation de la récursivité (car une pile de données est clairement nécessaire pour ça ...) Référence: en.wikipedia.org/wiki/PIC_microcontroller#Stacks
Ale
1

BASIC, à l'époque des numéros de ligne, avait tendance à avoir un support de récursivité médiocre. De nombreux (tous?) BASIC de cette époque prenaient en charge les appels gosub imbriqués, mais ne prenaient pas en charge un moyen facile de transmettre des paramètres ou de renvoyer des valeurs d'une manière qui le rendait utile pour l'auto-appel.

De nombreux premiers ordinateurs ont eu des problèmes de récursivité, car ils ont utilisé des instructions d'appel qui ont écrit l'adresse de retour au début de la routine appelée (PDP8, la famille de machines IAS, probablement plus d'architectures que je ne connais pas), généralement de telle manière qu'elle était le code machine pour "Aller à l'instruction après celle qui a appelé la routine".

Vatine
la source
1

Cela dépend de ce que vous entendez par « soutien ». Pour prendre en charge la récursivité, vous avez besoin d'une pile où ré-instancier des variables locales à chaque ré-entrée.

Même si le langage n'a pas le concept de variables locales, s'il a le concept de "sous-programme" et a un moyen de gérer une indexation entre des variables identiques (aka tableau) vous pouvez incrémenter / décrémenter un index global à chaque entrée / sortie d'une fonction et accéder à travers elle à un membre d'un ou plusieurs tableaux.

Je ne sais pas si cela peut être appelé "support". Les faits sont que j'ai écrit la fonction récursive avec le ZX-Spectrum BASIC, comme je l'ai fait dans Fortran77 comme dans COBOL ... toujours avec cette astuce.

Emilio Garavaglia
la source
1

Le langage d'assemblage ne prend pas directement en charge la récursivité - vous devez "le faire vous-même", généralement en poussant les paramètres sur la pile de la machine.

mikera
la source
2
Il prend en charge la récursivité dans la mesure où il prend en charge les appels de méthode. Il y a généralement une CALLinstruction, qui pousse automatiquement l'IP vers la pile avant de passer au sous-programme, et une RETinstruction qui insère l'adresse de retour dans l'IP. Il n'y a aucune raison pour laquelle vous ne pouvez pas CALLcréer votre propre point d'entrée.
Blorgbeard
@Blorgbeard - tout à fait vrai, même si je dirais que cela ne suffit pas à compter comme "prend en charge la récursivité" dans le sens commun car il ne gère pas les paramètres nécessaires pour l'appel récursif.
mikera
1
Eh bien, les appels récursifs n'ont techniquement pas besoin de paramètres, non? void f() { f(); }est récursif.
Blorgbeard
Techniquement, non. Mais être capable de coder un cas trivial ne signifie pas à mon humble avis que vous devriez décrire l'assemblage comme "supportant la récursivité". La plupart des utilisations pratiques de la récursivité nécessitent des paramètres.
mikera
Je suppose que vous pourriez dire cela. Mais dans ce cas, l'assemblage ne prend pas non plus en charge les boucles (vous devez manuellement CMP et JNZ). Je suppose que c'est une question de ce que vous appelez «soutenir».
Blorgbeard