Recursividad

RECURSIVIDAD
Este manual explica los procedimientos básicos para realizar algoritmos

recursivos, para procesos mas avanzados y entender mas a fondo,
recomiendo leer el documento “Metodología de la Programación II,
Recursividad”
Concepto
La recursividad constituye una de las

herramientas más potentes en programación. Es
un concepto matemático conocido.
Una función que se llama a sí misma se

denomina recursiva
Podemos usar recursividad si la solución de un

problema está expresada en función de si misma,
aunque de menor tamaño y conocemos la
solución no-recursiva para un determinado caso.
Ventajas y Desventajas
●Ventajas: No es necesario definir la secuencia

de pasos exacta para resolver el problema.
Desventajas: Podría ser menos eficiente.

●
Para que una definición recursiva esté
completamente identificada es necesario tener un
caso base que no se calcule utilizando casos
anteriores y que la división del problema converja
a ese caso base.
Diseño
Para resolver un problema, el primer paso será la

identificación de un algoritmo recursivo, es decir,
descomponer el problema de forma que su
solución quede definida en función de ella misma
pero para un tamaño menor y la tarea a realizar
para un caso simple.
Tendremos que diseñar: casos base, casos

generales y la solución en términos de ellos.
Caso Base
Son los casos del problema que se resuelve con

un segmento de código sin recursividad.
La cantidad y forma de los casos base son

arbitrarios, aunque la solución sera mejor
mientras mas simple y eficiente sea el conjunto
de casos seleccionados
Siempre debe existir al menos un caso base

Casos Generales
Si el problema es suficientemente complejo, la
solución se expresa, de forma recursiva, como la
unión de:
● La solución de uno o más subproblemas (de

igual naturaleza pero menor tamaño).
● Un conjunto de pasos adicionales. Estos pasos

junto con las soluciones a los subproblemas
componen la solución al problema general que
queremos resolver.
Casos Generales
Los casos generales siempre deben avanzar

hacia un caso base. Es decir, la llamada
recursiva se hace a un subproblema más a
pequeño y, en ultima instancia, los casos
generales alcanzaron un caso base.
Ejemplo: Factorial
1 , Si n = 0 CASO BASE
n! =
n·(n-1)! , Si n > 0
Ejemplo: Factorial
Ejemplo: Factorial
Tipos de Seguimiento
Existen tres formas de hacer un seguimiento a un

algoritmo recursivo:
● Calculo Matemático
● Recorrido por Pila
● Recorrido por Cascada
Para seguir con el código anterior verificaremos el

factorial de 3 (3!)
3!
Calculo Matemático
Calculo Matemático
Recorrido por Pila
En general, en la pila se almacena el entorno

asociado a las distintas funciones que se van
activando.
En particular, en un módulo recursivo, cada

llamada recursiva genera una nueva zona de
memoria en la pila independiente del resto de
llamadas.
Recorrido por Pila
Dentro de factorial, cada llamada

return n*factorial(n-1);
genera una nueva zona de memoria en la pila,
siendo n-1 el correspondiente parámetro actual
para esta zona de memoria y queda pendiente
la evaluación de la expresión y la ejecución del
return.
return
Recorrido por Pila
El proceso anterior se repite hasta que la

condición del caso base se hace cierta.
● Se ejecuta la sentencia return 1;

● Empieza la vuelta atrás de la excursión, se
evalúan las expresiones y se ejecutan los return
que estaban pendientes.
Recorrido por Pila
Recorrido por Pila
Recorrido en Cascada
Se representan en cascada cada una de las

llamadas al módulo recursivo, así como sus
respectivas zonas de memoria y los valores
que devuelven.
Cascada
¿Recursividad o Iteración?
1. La carga computacional (tiempo-espacio), asociada de
una llamada a una función y el retorno a la función que
hace la llamada.
2. Algunas soluciones recursivas pueden hacer que la
solución para un determinado tamaño del problema se
calcule varias veces.
3. Muchos problemas recursivos tienen como caso base
la resolución del problema para un tamaño muy
reducido. En ocasiones resulta excesivamente
pequeño.
4. La solución iterativa (igual de eficiente) puede ser muy
compleja de encontrar.
5. La solución recursiva es muy concisa, legible y
elegante.
Elaborado por:
Juan José Ramírez Lama

http://www.juaramir.com

Recursividad

Cargado por

Copyright:

Formatos disponibles

Recursividad

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Recursividad

Cargado por

Copyright:

Formatos disponibles

RECURSIVIDAD

Este manual explica los procedimientos básicos para realizar algoritmos

La recursividad constituye una de las

Una función que se llama a sí misma se

Podemos usar recursividad si la solución de un

●Ventajas: No es necesario definir la secuencia

Desventajas: Podría ser menos eficiente.

Para resolver un problema, el primer paso será la

Tendremos que diseñar: casos base, casos

Son los casos del problema que se resuelve con

La cantidad y forma de los casos base son

Siempre debe existir al menos un caso base

● La solución de uno o más subproblemas (de

● Un conjunto de pasos adicionales. Estos pasos

Los casos generales siempre deben avanzar

Existen tres formas de hacer un seguimiento a un

● Recorrido por Cascada

Para seguir con el código anterior verificaremos el

En general, en la pila se almacena el entorno

En particular, en un módulo recursivo, cada

Dentro de factorial, cada llamada

El proceso anterior se repite hasta que la

● Se ejecuta la sentencia return 1;

Se representan en cascada cada una de las

Juan José Ramírez Lama

También podría gustarte