Entendiendo la recursión

Contenido

Introducción 15

Parte 1. Conceptos 17 Definiciones 19 Esquema de una solución recursiva 25 Introducción 25 Pensando de forma recursiva 26 El problema de calcular la cantidad de cifras de un número dado 28 El problema de determinar si un número es par 29 El problema de determinar si un número es primo 30 El problema de calcular el residuo de la división entre dos números 32 El problema de calcular la suma de los números entre uno y un número dado 32 Ejemplos 34 Calcular el factorial de un número entero positivo 35 Calcular la potencia de dos números enteros positivos 37 Calcular la potencia de forma más eficiente 38 Calcular un término dado de la serie de Fibonacci 39 Calcular el máximo común divisor de dos números enteros 40 Calcular la suma de dos números enteros positivos 42 Ejercicios propuestos 43 Funcionamiento de la recursión 47 Introducción 47 Acciones que se realizan 47 Ejemplo práctico 49 Tiempos de ejecución 62 Clases de recursión 63 Recursión lineal o simple 63 Recursión lineal de cola 64 Recursión lineal no de cola 65 Recursión directa 65 Recursión indirecta, mutua o cruzada 66 Recursión múltiple 68 Recursión versus iteración 71 Problemática 71 Ventajas y desventajas de utilizar recursión 75 Ventajas que presenta el uso de la recursión 76 Desventajas del uso de la recursíón 76 Eliminación de la recursión 79 Eliminar recursión lineal de cola 79 Eliminar recursión lineal no de cola 82 Eliminar recursión no lineal de cola 85 Eliminar recursión no lineal no de cola 87


Parte 2. Solución de problemas 91 Manejo de arreglos 93 Definiciones 93 Arreglos de una dimensión - vectores 93 Ejercicios resueltos con vectores 95 Mostrar recursivamente el contenido de un arreglo o vector en orden inverso (desde el último hasta el primero) 95 Mostrar recursivamente el contenido de un arreglo en orden normal o directo (desde el primero hasta el último) 96 Sumar recursivamente el contenido de un vector de números enteros utilizando un acumulador y recorriendo el arreglo en orden inverso (del último al primer elemento) 97 Sumar recursivamente el contenido de un vector de números enteros sin acumulador y recorriendo el arreglo en orden inverso (desde el último hasta el primer elemento) 98 Invertir recursivamente el contenido de un vector que contiene números enteros 99 Encontrar de forma recursiva el mayor elemento de un arreglo conformado por números enteros recorriendo desde el último hasta el primer elemento 100 Determinar recursivamente si un vector que contiene los dígitos de un número cumple con las características de capicúa (que se lee igual de izquierda a derecha que de derecha a izquierda) 101 Manejo de arreglos de dos dimensiones - matrices 102 Ejercicios resueltos con matrices 104 Mostrar recursivamente el contenido de una matriz 104 Calcular recursivamente la traza de una matriz que contiene números enteros (suma de los elementos de la diagonal principal) 106 Sumar recursivamente el contenido de una matriz con números enteros 107 Calcular la matriz transpuesta de una matriz dada que contiene números enteros 108 Ejercicios propuestos 110 El problema de la búsqueda 111 Introducción 111 Búsqueda recursiva desde el final del arreglo 111 Búsqueda recursiva desde el principio del arreglo incrementando el índice de búsqueda en uno hasta llegar a su final 113 Búsqueda binaria en un arreglo no ordenado 114 Búsqueda binaria en un arreglo ordenado ascendentemente 116 El problema de los ordenamientos 119 Introducción 119 Ordenamiento por burbuja 119 Ordenamiento por intercambio 121 Ordenamiento por inserción 124 Ordenamiento rápido 125 Ordenamiento por mezcla 128 Ordenamiento por montículo 131 Programación dinámica 135 Introducción 135 Forma general 136 Problemas resueltos 137 Calcular el factorial de un número entero positivo 137 Calcular el n-ésimo término de la serie de Fibonacci 138 Cálculo del coeficiente binomial 140 Cálculo de la potencia de dos números enteros positivos 142 Calcular los factores primos de un número entero positivo 143 Ejercicios propuestos 146 Técnica de vuelta atrás o retroceso 149 Introducción 149 Forma general 150 Problemas resueltos 151 Subconjuntos de un conjunto 151 Encontrar todos los subconjuntos que sumen un valor dado 153 Hallar todas las permutaciones de un conjunto de números enteros 155 Acomodar ocho (8) reinas en un tablero de ajedrez de tal manera que no se ataquen unas a otras 157 El juego del sudoku 164 Ejercicios propuestos 168 Manejo de árboles binarios y grafos 171 Introducción 171 Definiciones 172 Representación 173 Representación de árboles binarios con arreglos 174 Representación de árboles con listas 176 Representación de grafos con matrices 176 Recorridos en un árbol binario 178 Recorrido en entre orden 178 Recorrido en preorden 179 Recorrido en posorden 180 Recorrido por niveles 181 Árboles binarios de búsqueda 183 Problemas resueltos con árboles y grafos 183 Cálculo de la altura de un árbol binario 183 Cálculo de la suma de los valores almacenados en los nodos de un árbol binario 185 Cálculo del mayor elemento de un árbol binario 186 Contabilizar el número de nodos de un árbol binario 186 Determinar si un árbol binario está balanceado 187 Coloreado de mapas 188 Búsqueda de caminos en un laberinto 194 Ejercicios propuestos 199 Técnica de divide y vencerás 201 Introducción 201 Forma general 202 Problemas resueltos 202 Las torres de Hanói 202 Determinar si un valor dado está almacenado en un árbol binario de búsqueda 205 Encontrar el máximo en un conjunto de n números 206 Dada una secuencia de n números enteros, encontrar el máximo valor que se puede obtener al sumar elementos consecutivos de la secuencia 209 Ejercicios propuestos 214 Referencias 215 Anexos 217 Anexo 1. Lenguaje algorítmico 217 Anexo 2. Implementación de la estructura de datos: pila 220 índice temático 223

La intención de escribir este libro es la de ayudar a las diferentes personas que, estando en el mundo de la programación de computadores, se enfrentan a resolver problemas mediante el concepto de la recursión. Esta palabra, que por sí sola asusta a muchos de quienes la abordan, de verdad es un gran instrumento que permite resolver innumerables problemas de una forma mucho más simple que al hacerlo iterativamente con otro tipo de estrategias y conceptos.

El tema lo planteamos luego de más de veinticinco (25) años de experiencia en el proceso de enseñanza-aprendizaje de asignaturas relacionadas con la programación de computadores, tiempo en el cual encontramos que aplicar recursión a la solución de problemas implica algo más que saber programar, incluye un componente de lógica que permite no solo el entendimiento del problema, sino la forma de expresar una o varias soluciones en términos recursivos. En los cursos impartidos hemos encontrado que la mayoría de los estudiantes no entienden el concepto, y que la sola palabra ya produce cierto bloqueo mental al tratar de solucionar un problema. Por esta y muchas otras razones consideramos que es importante hacer especial énfasis en que los estudiantes y amantes de la programación entiendan, apliquen y hagan un buen uso de los conceptos que involucra la recursión.

Todo programador se debe enfrentar a los diferentes paradigmas que tiene la programación, y siempre serán estos conceptos los que le permitan desarrollar habilidades y destrezas que con el apoyo de las teorías matemáticas le hagan posible llegar a resolver un número considerable de problemas de diferente dificultad y complejidad.

En este libro se plantea el concepto de recursión a partir de su origen, sus usos y aplicaciones, de manera que permita a quienes lo lean llegar a establecer las diferentes estrategias que de allí se derivan y que posibilitarán la solución de muchos problemas.