Cap tulo 18 Deitel 18 0765 0797
Páginas: 55 (13503 palabras)
Publicado: 29 de abril de 2015
Recursividad
18
Debemos aprender a explorar
todas las opciones y posibilidades
a las que nos enfrentamos en un
mundo complejo, que evoluciona
rápidamente.
—James William Fulbright
Oh, maldita iteración, que eres
capaz de corromper hasta a un
santo.
—William Shakespeare
Es un pobre orden de memoria,
que sólo funciona al revés.
—Lewis Carroll
La vida sólo puede comprenderse
al revés; pero debevivirse hacia
delante.
—Soren Kierkegaard
Objetivos
En este capítulo aprenderá a:
■ Comprender el concepto
de recursividad.
■ Escribir y utilizar métodos
recursivos.
■ Determinar el caso base y el
paso de recursividad en un
algoritmo recursivo.
■ Conocer cómo el sistema
maneja las llamadas a métodos
recursivos.
■ Conocer las diferencias entre
recursividad e iteración,
y cuándo es apropiadoutilizar cada una.
■ Conocer las figuras geométricas
llamadas fractales, y cómo se
dibujan mediante la recursividad.
■ Conocer el concepto de “vuelta
atrás” recursiva (backtracking),
y por qué es una técnica
efectiva para solucionar
problemas.
766
Capítulo 18 Recursividad
18.1 Introducción
18.6 Comparación entre recursividad e iteración
18.2 Conceptos de recursividad
18.7 Las torres de Hanoi18.3 Ejemplo de uso de recursividad: factoriales
18.8 Fractales
18.4 Ejemplo de uso de recursividad: serie
de Fibonacci
18.9 “Vuelta atrás” recursiva (backtracking)
18.10 Conclusión
18.5 La recursividad y la pila de llamadas
a métodos
Resumen | Ejercicios de autoevaluación | Respuestas a los ejercicios de autoevaluación | Ejercicios
18.1 Introducción
Los programas que hemos visto hasta ahoraestán estructurados en general como métodos que se llaman entre sí, de una manera jerárquica. Para algunos problemas, es conveniente hacer que un método
se llame a sí mismo. Dicho método se conoce como método recursivo; este método se puede llamar
en forma directa o indirecta a través de otro método. La recursividad es un tema importante, que puede
tratarse de manera extensa en los cursos de cienciascomputacionales de nivel superior. En este capítulo consideraremos la recursividad en forma conceptual, y después presentaremos varios programas
que contienen métodos recursivos. En la figura 18.1 se sintetizan los ejemplos y ejercicios de recursividad que se incluyen en este libro.
Capítulo
Ejemplos y ejercicios de recursividad en este libro
18
Método factorial (figuras 18.3 y 18.4)
MétodoFibonacci (figura 18.5)
Torres de Hanoi (figuras 18.11)
Fractales (figuras 18.18 y 18.19)
¿Qué hace este código? (ejercicios 18.7, 18.12 y 18.13)
Encuentre el error en el siguiente código (ejercicio 18.8)
Elevar un entero a una potencia entera (ejercicio 18.9)
Visualización de la recursividad (ejercicio 18.10)
Máximo común divisor (ejercicio 18.11)
Determinar si una cadena es un palíndromo(ejercicio 18.14)
Ocho reinas (ejercicio 18.15)
Imprimir un arreglo (ejercicio 18.16)
Imprimir un arreglo en forma inversa (ejercicio 18.17)
Mínimo valor en un arreglo (ejercicio 18.18)
Fractal de estrella (ejercicio 18.19)
Recorrido de laberinto usando la “vuelta atrás” recursiva (ejercicio 18.20)
Generación de laberintos al azar (ejercicio 18.21)
Laberintos de cualquier tamaño (ejercicio 18.22)
Tiemponecesario para calcular un número de Fibonacci (ejercicio 18.23)
19
Ordenamiento por combinación (figuras 19.10 y 19.11)
Búsqueda lineal (ejercicio 19.8)
Búsqueda binaria (ejercicio 19.9)
Quicksort (ejercicio 19.10)
Fig. 18.1 Η Resumen de los ejemplos y ejercicios de recursividad en este libro (parte 1 de 2).
18.2 Conceptos de recursividad
Capítulo
Ejemplos y ejercicios de recursividad eneste libro
22
(en inglés)
Inserción en árbol binario (figura 22.17)
Recorrido preorden de un árbol binario (22.17)
Recorrido inorden de un árbol binario (22.17)
Recorrido postorden de un árbol binario (22.17)
Imprimir una lista enlazada en forma inversa (ejercicio 22.20)
Buscar en una lista enlazada (ejercicio 22.21)
767
Fig. 18.1 Η Resumen de los ejemplos y ejercicios de recursividad en este...
18
Debemos aprender a explorar
todas las opciones y posibilidades
a las que nos enfrentamos en un
mundo complejo, que evoluciona
rápidamente.
—James William Fulbright
Oh, maldita iteración, que eres
capaz de corromper hasta a un
santo.
—William Shakespeare
Es un pobre orden de memoria,
que sólo funciona al revés.
—Lewis Carroll
La vida sólo puede comprenderse
al revés; pero debevivirse hacia
delante.
—Soren Kierkegaard
Objetivos
En este capítulo aprenderá a:
■ Comprender el concepto
de recursividad.
■ Escribir y utilizar métodos
recursivos.
■ Determinar el caso base y el
paso de recursividad en un
algoritmo recursivo.
■ Conocer cómo el sistema
maneja las llamadas a métodos
recursivos.
■ Conocer las diferencias entre
recursividad e iteración,
y cuándo es apropiadoutilizar cada una.
■ Conocer las figuras geométricas
llamadas fractales, y cómo se
dibujan mediante la recursividad.
■ Conocer el concepto de “vuelta
atrás” recursiva (backtracking),
y por qué es una técnica
efectiva para solucionar
problemas.
766
Capítulo 18 Recursividad
18.1 Introducción
18.6 Comparación entre recursividad e iteración
18.2 Conceptos de recursividad
18.7 Las torres de Hanoi18.3 Ejemplo de uso de recursividad: factoriales
18.8 Fractales
18.4 Ejemplo de uso de recursividad: serie
de Fibonacci
18.9 “Vuelta atrás” recursiva (backtracking)
18.10 Conclusión
18.5 La recursividad y la pila de llamadas
a métodos
Resumen | Ejercicios de autoevaluación | Respuestas a los ejercicios de autoevaluación | Ejercicios
18.1 Introducción
Los programas que hemos visto hasta ahoraestán estructurados en general como métodos que se llaman entre sí, de una manera jerárquica. Para algunos problemas, es conveniente hacer que un método
se llame a sí mismo. Dicho método se conoce como método recursivo; este método se puede llamar
en forma directa o indirecta a través de otro método. La recursividad es un tema importante, que puede
tratarse de manera extensa en los cursos de cienciascomputacionales de nivel superior. En este capítulo consideraremos la recursividad en forma conceptual, y después presentaremos varios programas
que contienen métodos recursivos. En la figura 18.1 se sintetizan los ejemplos y ejercicios de recursividad que se incluyen en este libro.
Capítulo
Ejemplos y ejercicios de recursividad en este libro
18
Método factorial (figuras 18.3 y 18.4)
MétodoFibonacci (figura 18.5)
Torres de Hanoi (figuras 18.11)
Fractales (figuras 18.18 y 18.19)
¿Qué hace este código? (ejercicios 18.7, 18.12 y 18.13)
Encuentre el error en el siguiente código (ejercicio 18.8)
Elevar un entero a una potencia entera (ejercicio 18.9)
Visualización de la recursividad (ejercicio 18.10)
Máximo común divisor (ejercicio 18.11)
Determinar si una cadena es un palíndromo(ejercicio 18.14)
Ocho reinas (ejercicio 18.15)
Imprimir un arreglo (ejercicio 18.16)
Imprimir un arreglo en forma inversa (ejercicio 18.17)
Mínimo valor en un arreglo (ejercicio 18.18)
Fractal de estrella (ejercicio 18.19)
Recorrido de laberinto usando la “vuelta atrás” recursiva (ejercicio 18.20)
Generación de laberintos al azar (ejercicio 18.21)
Laberintos de cualquier tamaño (ejercicio 18.22)
Tiemponecesario para calcular un número de Fibonacci (ejercicio 18.23)
19
Ordenamiento por combinación (figuras 19.10 y 19.11)
Búsqueda lineal (ejercicio 19.8)
Búsqueda binaria (ejercicio 19.9)
Quicksort (ejercicio 19.10)
Fig. 18.1 Η Resumen de los ejemplos y ejercicios de recursividad en este libro (parte 1 de 2).
18.2 Conceptos de recursividad
Capítulo
Ejemplos y ejercicios de recursividad eneste libro
22
(en inglés)
Inserción en árbol binario (figura 22.17)
Recorrido preorden de un árbol binario (22.17)
Recorrido inorden de un árbol binario (22.17)
Recorrido postorden de un árbol binario (22.17)
Imprimir una lista enlazada en forma inversa (ejercicio 22.20)
Buscar en una lista enlazada (ejercicio 22.21)
767
Fig. 18.1 Η Resumen de los ejemplos y ejercicios de recursividad en este...
Leer documento completo
Regístrate para leer el documento completo.