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