Recursividad

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’,......

1. Aritmética

Sea 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.

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...

1. Búsqueda por dicotomía en una tabla ordenada

El capítulo «Iteración» ha resuelto el problema definiendo una función iterativa.

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...