Propiedades de las definiciones o algoritmos recursivos:
Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una “salida” de la secuencia de llamadas recursivas.
Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos más simples no recursivos.
Cadenas recursivas
Una función recursiva no necesita llamarse a si misma de manera directa. En su lugar, puede hacerlo de manera indirecta como en el siguiente ejemplo:
A(formal parameters) b(formal parameters){
B(argument);
a(argument);
}
En este ejemplo la función a llama a b, la cual puede a su vez llamar a a, que puede llamar de nuevo a b. asi, ambas funciones a y b son recursivas, dado que se llaman a si mismo de manera indirecta. Sin embargo, el que sea no es obvio a partir del examen del cuerpo de una de las rutinas en forma individual. La rutina a, parece llamar a la rutina b y es posible determinar que se puede llamar a si misma de manera indirecta al examinar solo a a.
Pueden incluirse más de dos rutinas en una cadena recursiva. Asi una rutina a puede llamar a b, que llama a c,…, que llama a z, que llama a a. cada rutina de la cadena puede potencialmente llamarse a sí misma y, por lo tanto es recursiva. Por supuesto, el programador debe asegurarse de que un programa de este tipo genere una secuencia infinita de llamadas recursivas.
Definición recursiva de expresiones algebraicas
Como ejemplo de cadena recursiva consideremos el siguiente grupo de definiciones:
a) una expresión es un término seguido de un signo más seguido por un término, o un término solo.
b) un término es un factor seguido por un asterisco seguido por un factor, o un factor solo.
c) un factor es una letra o una expresión encerrada entre paréntesis.
La forma más simple de un factor es una letra. Así A, B, C, Q, Z y M son factores. También son términos, dado que un término puede ser un factor solo. También son expresiones dado que una expresión puede ser un término solo. Como A es una expresión, (A) es un factor y, por lo tanto, un término y una expresión. A+B es un ejemplo de una expresión que no es un término ni un factor, sin embargo (A+B) es las tres cosas. A*B es un término y, en consecuencia, una expresión, pero no es un factor. A*B+C son expresiones es una expresión, pero no es un factor.
Cada uno de los ejemplos anteriores es una expresión valida. Esto puede mostrarse al aplicar la definición de una expresión a cada uno. Considérese, sin embargo la cadena A+*B. no es ni una expresión, ni un factor. Seria instructivo para el lector intentar aplicar la definición de expresión, termino y factor para ver que ninguna de ellas describe la cadena A+*B. de manera similar, (A+B*)C y A+B+C son expresiones nulas de acuerdo con las definiciones precedentes.