La respuesta intuitiva es que si no tiene bucles ilimitados y no tiene recursividad y no tiene goto, sus programas terminan. Esto no es del todo cierto, hay otras formas de infiltrar la no terminación, pero es lo suficientemente bueno para la mayoría de los casos prácticos. Por supuesto, lo contrario es incorrecto, hay lenguajes con estas construcciones que no permiten programas sin terminación, pero utilizan otros tipos de restricciones, como sistemas de tipos sofisticados.
Recursividad
Una restricción común en los lenguajes de scripting es prevenir dinámicamente la recursividad: si A llama a B llama a C llama ... llama a A, entonces el intérprete (o el verificador, en su caso) se da por vencido o señala un error, incluso si la recursión realmente podría terminar. Dos ejemplos concretos:
El preprocesador C deja una macro intacta mientras está expandiendo esa macro. El uso más común es definir un contenedor alrededor de una función:
#define f(x) (printf("calling f(%d)\n", (x)), f(x))
f(3);
Esto se expande a
(printf("calling f(%d)\n", (3)), f(3))
La recursividad mutua también se maneja. Una consecuencia es que el preprocesador C siempre termina, aunque es posible construir macros con alta complejidad de tiempo de ejecución.
#define f0(x) x(x)x(x)
#define f1(x) f0(f0(x))
#define f2(x) f1(f1(x))
#define f3(x) f2(f2(x))
f3(x)
Los shells de Unix expanden los alias de forma recursiva, pero solo hasta que encuentran un alias que ya se está expandiendo. Nuevamente, el propósito principal es definir un alias para un comando con un nombre similar.
alias ls='ls --color'
alias ll='ls -l'
nn
Existen técnicas más generales para demostrar que las llamadas recursivas terminan, como encontrar un número entero positivo que siempre disminuye de una llamada recursiva a la siguiente, pero son mucho más difíciles de detectar. A menudo son difíciles de verificar, y mucho menos inferir.
Bucles
for
mn
En particular, con bucles for (más construcciones de lenguaje razonables como condicionales), puede escribir todas las funciones recursivas primitivas , y viceversa. Puede reconocer sintácticamente las funciones recursivas primitivas (si están escritas de manera no ofuscada), porque no usan el bucle while o goto o la recursión u otro truco. Se garantiza que las funciones recursivas primitivas terminarán, y la mayoría de las tareas prácticas no van más allá de la recursividad primitiva.
Gilles 'SO- deja de ser malvado'
fuente