Conceptos generales de recursividad

CONCEPTOS GENERALES DE
LA RECURSIVIDAD
1- Definición de recursividad
2- Tipos de recursividad
3- Normas de la recursividad
4- Ejemplo típico del factorial
5- Verificación de la recursividad
6- Funcionamiento de la recursividad
7- Depuración de programas recursivos
8- Ventajas y desventajas

1- DEFINICIÓN DE RECURSIVIDAD
• Herramienta poderosa de programación
• Ofrecida por la mayoríade los lenguajes de
programación
• Forma general: un objeto es recursivo cuando en
su definición encontramos referencias al mismo
objeto
• Desde programación: un programa permite que se
haga referencia a sí mismo dentro de su
especificación

• Una llamada a un programa recursivo genera una
o mas llamadas al mismo programa
• Cada una de esas llamadas genera nuevas
invocaciones y asísucesivamente
• Cada llamada resuelve una versión mas pequeña
del problema original
• Las cadenas de llamadas terminan al encontrar un
caso base que no genera nuevas invocaciones
• Así el control del programa se devuelve a la
llamada anterior que, a su vez, cuando termina
devuelve el control a la anterior, y así
sucesivamente hasta que todas las cadenas de
llamadas terminen

•Recursividad e iteración: los dos
mecanismos de programación para describir
procesos repetitivos
• Diseño iterativo: se le ha dedicado bastante
estudio, quizás por razones históricas de la
estructura de las computadoras
• Lenguajes como LISP y PROLOG pueden
prescindir de la iteración y utilizar la
recursividad como único mecanismo de
repetición de cálculos

2- TIPOS DE RECURSIVIDAD
• Directa osimple
– Cuando un programa A se llama a sí mismo una
o mas veces directamente
• A
A
• Indirecta o mutua
– Cuando un programa A llama a un programa B,
y éste a su vez llama al programa A
• A
B
A

3- NORMAS DE LA RECURSIVIDAD
• Obtener especificación detallada del problema
• Diseñar casos base: casos del problema que se
resuelven sin recursividad. Debe existir al menos
un caso baseque garantize el el algoritmo va a
terminar.
• Diseñar casos generales: descomponer el
problema en subproblemas, los cuales se resuelven
apoyándose con el algoritmo que ya se tiene. Estas
soluciones deben llevarnos hacia un caso base.
• Probar que los casos base y generales encuentran
solución.

4- EJEMPLO TÍPICO DEL FACTORIAL
• n! se define como el producto de todos los enteros
entren y 1. Por definición el factorial de 0 es 1.
• Definición matemática
– Si n=0 el factorial es 1
– Si n>0 el factorial es n*(n-1)*(n-2)* ... *2*1
• Para n=4, el factorial (4!) es 4*3*2*1=24
• Se puede expresar también así:
– 4! = 4 * 3!
– 3! = 3 * 2!
– 2! = 2 * 1!
– 1! = 1 * 0!
– 0! = 1
• Definición recursiva
– Si n=0 el factorial es 1
– Si n>0 el factorial es n*(n-1)!

• De estadefinición se puede escribir una función
recursiva:
Function Factorial (N: integer): word ;
Begin
If N = 0 Línea 1
Then Factorial := 1 Línea 2 Caso base
Else Factorial := N * Factorial (N-1)Línea3 Caso general
End;

Seguimiento del factorial de 4 (4!)
Línea Acción
#1 4 no es igual a 0, por ello saltar a cláusula else
#3 Factorial := 4 * Factorial (4-1)
La primera llamada recursiva nosdevuelve al comienzo de
la función, con N = 3
#1 3 no es igual a 0, por ello saltar a cláusula else
#3 Factorial := 3 * Factorial (3-1)
La segunda llamada recursiva nos devuelve al comienzo de
la función, con N =2

Línea Acción
#1 2 no es igual a 0, por ello saltar a cláusula else
#3 Factorial := 2 * Factorial (2-1)
La tercera llamada recursiva nos devuelve al comienzo de
la función, conN = 1
#1 1 no es igual a 0, por ello saltar a cláusula else
#3 Factorial := 1 * Factorial (1-1)
La cuarta llamada recursiva nos devuelve al comienzo de
la función, con N = 0

#1 0 es igual a 0, por ello ir a la línea #2
#2 Factorial := 1
El valor de Factorial (0) es devuelto a la sentencia
llamadora:
La cuarta llamada recursiva
#3 Factorial := 1 * Factorial (0) = 1 * 1 = 1
El valor...