Ediciones ENI Editorial | líder en informática
Recursividad
Introducción
Este capítulo es el segundo que introduce el concepto de repetición en los tratamientos de los datos después del capítulo «Iteración». Sin embargo, mientras que en los capítulos anteriores los cambios de estados del sistema se obtenían con instrucciones que indicaban explícitamente las modificaciones que se tenían que realizar en los datos, aquí se obtienen dando una definición de estos cambios. En particular, los tratamientos no usan la instrucción de asignación, salvo en contadas ocasiones, para dar un valor a la pseudovariable Resultado con el fin de precisar lo que calcula y devuelve una función.
La segunda sección introduce la recursividad en los tratamientos con cadenas de caracteres. Se muestra qué es una definición recursiva y se aplica este tipo de definición a la especificación de algoritmos con cadenas de caracteres. La siguiente sección da algunos ejemplos de especificaciones o de tratamientos recursivos con los números. Para terminar, la cuarta sección empieza el estudio de un problema con el que nos encontramos a menudo: la edición de un número. Se trata de transformar un número dado para obtener los caracteres que representan su valor en una base de numeración dada.
Introducción a la recursividad: las cadenas de caracteres
La recursividad se introduce en esta sección como un método general de especificación algorítmica de los algoritmos. Esta frase ya es por sí misma una frase que formula una propiedad recursiva: la especificación de un algoritmo es un algoritmo.
La primera parte presenta la recursividad con un ejemplo sencillo: la definición de una palabra del idioma. La segunda parte estudia ejemplos de especificaciones recursivas de algoritmos de tratamiento con las cadenas de caracteres. La tercera parte da la solución completa de algunos ejercicios didácticos y, finalmente, la última, propone resolver diversos ejercicios cuya solución no se ha desarrollado aquí.
1. Presentación de la recursividad
Consideremos una palabra. Una palabra es una cadena de caracteres de longitud finita. Para simplificar esta presentación, se restringe a las palabras, sean o no del idioma, escritas en minúsculas y sin caracteres acentuados: ‘casa’, ‘pescado’ o ‘coche’ son ejemplos de palabras que nos interesan. ‘Colegio’, ‘Mansión’ o ‘elección’ están excluidas porque contienen caracteres acentuados o mayúsculas.
¿Cómo dar una definición formal de una palabra?
Se trata de dar una definición que se aplica a una palabra cualquiera, sin acentos ni mayúsculas, como ya hemos mencionado. Se puede dar la siguiente definición:
Definición 1
Una palabra puede ser un carácter o un carácter seguido de una palabra.
Dicho de otra manera, una palabra, seleccionada entre las permitidas, puede ser una cadena de caracteres reducida a un único carácter o, si no, una cadena de caracteres formada por un primer carácter seguido de otra palabra.
Así, por ejemplo, la palabra ‘casa’ está formada por el carácter ‘c’ seguido de la palabra ‘asa’. La palabra ‘asa’ está formada por ‘a’ seguido de la palabra ‘sa’ y así sucesivamente. Ahora es suficiente con decir qué es un carácter. Se puede definir un carácter mediante una enumeración.
Definición 2
Un carácter es un elemento del conjunto {’a’, ’b’,......
Los números y la recursividad
Los números proporcionan numerosos ejemplos sencillos de recursividad. De hecho, las definiciones matemáticas a menudo son recursivas. Esta sección le propone algunos ejercicios sobre este tema. Los que se lleven bien con las matemáticas pueden pasar a la sección siguiente.
1. Aritmética
el conjunto
de los números enteros: = { ..., -2, -1, 0, 1, 2,
...}. Se supone que las únicas operaciones
actualmente definidas en son sucesor, que devuelve el sucesor
de un número entero en la lista ordenada de sus elementos,
y predecesor, la función
dual del anterior.|
Ejercicio 6: Aritmética con los números enteros |
1. Escribir el algoritmo de la suma de dos números enteros.
2. Escribir el algoritmo que devuelve el opuesto de un número entero.
La diferencia de los dos números enteros en la suma del primero con el opuesto del segundo.
3. Escribir el algoritmo que calcula la diferencia de dos números enteros.
El producto de dos números enteros se calcula haciendo una suma repetida. Así, por ejemplo, 7 x 5 es la suma de 5 términos iguales a 7.
4. Escribir los algoritmos de la multiplicación y de la división.
Puede encontrar la solución de este ejercicio en los complementos disponibles para descargar desde la página Información.
2. Factorial y otros ejercicios usados...
Números y cadenas de caracteres: edición de un número entero
A menudo nos encontramos con el problema de la edición de un número entero en distintos contextos. Esta sección aborda este problema, con el que tendremos ocasión de volvernos a encontrar en los capítulos posteriores y especialmente en el capítulo «Edición de un número», donde se desarrollará su estudio.
En español, la palabra cifra se utiliza con varios sentidos. A menudo designa un número entero inferior estrictamente a la base de numeración por ejemplo, un número entero comprendido entre 0 y 9 en base diez. También designa el carácter que representa a uno de estos números; por ejemplo, el carácter ’7’, que representa al número 7. También tiene otros sentidos; un diccionario permite darse cuenta de la riqueza polisémica de esta palabra.
Vamos a quedarnos en base diez para simplificar. Tenemos que distinguir con sumo cuidado un número estrictamente inferior a diez del carácter que representa este número. Entonces es necesario hacer una diferencia bien marcada entre el objeto matemático, el número, que es independiente de su representación, y la cifra que lo representa en un sistema de codificación particular. Así, el número de días de la semana está representado por la cadena de caracteres ‘siete’, por la cifra ’7’, por la serie de cifras, es decir, la cadena de caracteres, ’111’ en base dos, etc. Lo que tenemos...
Problemas
Esta sección plantea algunos problemas más difíciles. Para resolverlos de una manera que luego sea viable para la programación, es necesario utilizar la reflexión y un poco de inventiva.
1. Búsqueda por dicotomía en una tabla ordenada
El capítulo «Iteración» ha resuelto el problema definiendo una función iterativa.
|
Ejercicio resuelto 5: Búsqueda recursiva por dicotomía en una tabla ordenada |
Se pide resolver el mismo problema definiendo una función recursiva.
Puede encontrar una solución estudiada de este ejercicio en los complementos disponibles para descargar desde la página Información.
2. Palíndromos
Se llama palíndromo a un texto que es el mismo que su imagen reflejada. Así, por ejemplo, las palabras ’SALAS’, ’oso’, ’26762’ son palíndromos. Es decir, un palíndromo se lee de derecha a izquierda como de izquierda a derecha.
Con esta definición, ’Salas’ u ’¡oso!’ ya no son palíndromos. En el primero, la letra mayúscula inicial y, en el segundo, el espacio y el signo de exclamación perturban la imagen espejo de la palabra. Igualmente, la frase ’Logré ver gol’ sería un palíndromo si la letra mayúscula al inicio de la frase fuera ’l’, si la letra ’é’ no estuviera acentuada y si se eliminaran los espacios.
¿Hay frases palíndromas? El problema se complica por los caracteres separadores, como el espacio, los signos de puntuación...
Resumen
Este capítulo ha introducido el concepto de tratamientos repetidos. Se elabora una definición de los cambios de los estados del software en lugar de decir explícitamente las transformaciones que experimentarán los datos. Así, se pueden definir los algoritmos enunciando cláusulas sin efectos secundarios para precisar la precondición, la poscondición y el invariante de su especificación. Los capítulos siguientes usarán la recursividad de manera intensiva. Por supuesto, es un concepto difícil de abordar para principiantes. Es completamente posible prescindir de él y expresar las especificaciones usando fórmulas procedentes de las matemáticas o del idioma español; pero en ese caso hay que estar atentos y seguir siendo rigurosos.