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 si n = 0 n! = n*(n?1)! 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 si b = 0 Suma(a, b) = Suma(a, b?1) + 1 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? Expresar la solución en
términos de la solución (o soluciones) a una
instancia menos grande del mismo problema Identificar un caso
trivial 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 si n = 0 (caso base) n! =
n*(n?1)! 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