Fichas
Algoritmos Recursivos
Fichas del conjunto (9)
- 1RecursividadTécnica consistente en definir una función en términos de sí misma. Puesto que en C una función puede llamar a otras funciones, se permite que una función también pueda llamarse a sí misma.
- 2Condición de salidaAlgoritmo recursivo, el cual conocemos su solución.
- 3Recursión simpleDecimos que una acción recursiva tiene recursión simple si cada caso recursivo
realiza exactamente una llamada recursiva. Abusando de la notación en las asignaciones, podemos describirlo mediante el esquema general - 4Recursión finalLa recursión final es un caso particular de recursión simple donde la
función de combinación se limita a transmitir el resultado de la llamada recursiva. Se llama final porque lo último que se hace en cada pasada es la llamadarecursiva.
El resultado será siempre el obtenido en uno de los casos base.
Los algoritmos recursivos finales tienen la interesante propiedad de que pueden ser traducidos de manera directa a soluciones iterativas, más eficientes. - 5Recursión múltipleEste tipo de recursión se caracteriza por que, al menos en un caso recursivo, se
realizan varias llamadas recursivas. - 6Planteamiento recursivoSe ha de encontrar una estrategia recursiva para alcanzar la postcondición, es decir, la solución. A veces, la forma de la postcondición, o de las operaciones que en ella aparecen, nos sugerirá directamente una estrategia recursiva.
- 7Análisis de casosSe trata de obtener las condiciones que permiten discriminar los casos directos de los recursivos. Deben tratarse de forma exhaustiva y mutuamente excluyente todos los casos contemplados en la
precondición - 8Caso directoHemos de encontrar la acción que resuelve el caso directo. Si hubiese más de un caso directo, repetiríamos este paso para cada uno de ellos.
- 9Descomposición recursivaSe trata de obtener la función sucesor s(xr) que nos proporciona los datos que empleamos para realizar la llamada recursiva. Si hay más de un caso recursivo, obtenemos la función sucesor para cada uno de ellos.
Información
- Descripción
- Matemáticas Discretas
- Creado por
- David Añadiendo
- Visitas
- 13
- Etiquetas
- Valoración