Download Recurrencia

Recurrencia
Programación II
20-21 de enero de 2009
Recurrencia
• Un concepto es recursivo si está definido
a partir de su mismo
• Ejemplo: los números naturales
– 0 es un número natural
– x es un número natural si x1 es un número
natural
• La definición de un número natural incluye
una referencia al concepto de números
naturales
Ejemplo: Factorial
• La factorial de un número natural n, que
se escribe n!, se puede definir de la
siguiente manera:
– n! = 1
– n! = n*(n1)!
si n = 0
si n > 0
• La factorial también es un concepto
recursivo, ya que se define a partir de su
misma
Ejemplo: Suma
• La suma de dos números naturales a y b
también se puede definir de manera
recursiva:
– Suma(a, b) = a
– Suma(a, b) = Suma(a, b1) + 1
si b = 0
si b > 0
• Aquí, la suma de a y b está definida a
partir de otra suma
Recurrencia
• Observamos que todos los ejemplos de
definiciones recursivas tienen dos partes
• Por un lado tenemos un caso elemental
– 0 es un número natural
– 0! = 1
– Suma(a, 0) = a
• Por otro lado tenemos una parte recursiva
• ¡Ambas partes son esenciales!
Ejemplo
• Calcular la factorial de 4, es decir, 4!
• 4 es mayor que 0, por lo que 4! se define
como 4! = 4*(41)! = 4*3!
• Para calcular 4! necesitamos calcular 3!
• 3 es mayor que 0, por lo que 3! = 3*2!
• 2 es mayor que 0, por lo que 2! = 2*1!
• 1 es mayor que 0, por lo que 1! = 1*0!
• La primera parte de la definición es 0! = 1
Ejemplo
• Ahora podemos calcular 4!:
0! = 1
1! = 1*0! = 1*1 = 1
2! = 2*1! = 2*1 = 2
3! = 3*2! = 3*2 = 6
4! = 4*3! = 4*6 = 24
Recurrencia
• Podemos identificar las dos partes de una
solución recursiva:
• Caso base: problema trivial que se puede
resolver sin cálculo
• Caso recursivo: la solución al problema
se define a partir de la solución de un
problema de la misma clase
Principio de Inducción
• El concepto de recurrencia es muy
parecido al Principio de Inducción
• Este principio permite demostrar una
propiedad P sobre los números naturales
de la siguiente manera:
Base de Inducción: Mostrar que P(0) es válida
Paso de Inducción: Para cualquier número
natural n > 0, si P(n1) es válida, P(n)
también lo es
Ejemplo
• Demostrar que para cualquier número
natural n, la suma 0+…+n es n*(n+1)/2
Base de Inducción: 0 = 0*1/2 = 0
Paso de Inducción: Por hipótesis de inducción,
la suma 0+…+(n1) es (n1)*n/2. Por lo tanto,
0+…+n = (0+…+(n1)) + n = {inducción} =
(n1)*n/2 + n =
(n2n+2n)/2 =
(n2+n)/2 = n*(n+1)/2
Principio de Inducción
• Observamos que las dos partes del
Principio de Inducción son muy parecidos
a las dos partes de una solución recursiva:
Base de Inducción  Caso base
Paso de Inducción  Caso recursivo
Recurrencia en la informática
• ¿Cómo implementar la recurrencia en un
programa?
• En la informática, la recurrencia se
implementa mediante funciones
• En particular, una función es recursiva si
llama a su misma
• El primer lenguaje de programación que
permitió funciones recursivas fue LISP
Resolver problemas
•
¿Cómo resolver un problema mediante
el uso de la recurrencia?
1) Expresar la solución en términos de la
solución (o soluciones) a una instancia
menos grande del mismo problema
2) Identificar un caso trivial
3) Comprobar que el caso trivial siempre se
cumple
Ejemplo: Factorial
• Escribir una función en pseudo-código que
calcule la factorial n! de un número natural
n
• La función debe aprovechar la definición
recursiva:
– n! = 1
– n! = n*(n1)!
si n = 0 (caso base)
si n > 0 (caso recursivo)
• Decimos que la función es recursiva
Ejemplo: Factorial
funcion Factorial(n:natural) devuelve natural
si (n=0) entonces
devuelve 1;
caso base
sino
devuelve n*Factorial(n-1);
fsi
ffuncion
caso recursivo
Recurrencia
• ¿Porqué escribir funciones recursivas?
• En la mayoría de los casos, una función
recursiva se puede reemplazar por una
función iterativa
• Sin embargo, muchas veces la definición
recursiva resulta más clara e intuitiva
• Permite definir funciones complejas de
manera muy compacta
Ejercicio
• Escribir una función que calcule la suma
de dos números naturales a y b, usando la
definición recursiva
Ejercicio
• Escribir una función recursiva que calcule
la suma de los elementos de un vector V
de números naturales
Ejercicio
• Escribir una función recursiva que calcule
el número de maneras de seleccionar k
elementos de un conjunto de n elementos