Universidad Mariano Gálvez de Guatemala
Facultad de Ingenieria en Sistemas
 
 News & Updates

 

 

Recursividad

La recursividad forma parte del repertorio para resolver problemas en Computación y es de los métodos más poderosos y usados.

 

Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.

 

La recursividad es un concepto fundamental en matemáticas y en computación. Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta describir.

 

En toda situación en la cual la respuesta pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la fórmula recursiva es un buen candidado para resolver el problema.

 

Los razonamientos recursivos se encuentran en la base misma de las matemáticas porque son necesarios para describir conceptos centrales como el de número:

 

Ejemplo:

 

1. Factorial

 

Definición:

 

            factorial (n) = n!                                 si n > 0

            factorial (n) = n*n-1*n-2* ... * 1          si n > 0

 

            el valor de 0! se define como

 

            factorial (0) = 1

 

Su definición recursiva es:

 

            factorial (n) = 1                                  si n = 0

            factorial (n) = n* factorial (n-1)          si n > 0

 

así para calcular el factorial de 4:

 

            factorial (4) = 4 * factorial (3) = 4 * 6 = 24

            factorial (3) = 3 * factorial (2) = 3 *2 = 6

            factorial (2) = 2 * factorial (1) = 2 * 1 = 2

            factorial (1) = 1 * factorial (0) = 1 * 1 = 1

 

estática int factorial (int n)

comienza

            si n = 0 entonces

                        regresa 1

            otro

                        regresa factorial (n-1) * n

termina

 

Versión iterativa:

 

estática int factorial (int n)

comienza

            fact ß 1

            para i ß 1 hasta n

                        fact ß i * fact

            regresa fact

termina

 

 

Las definiciones recursivas de funciones en matemáticas que tienen como argumentos números enteros, se llaman relaciones de recurrencia.

 

Forma de una ecuación de recurrencia:

 

coar +c1ar-1 + c2ar-2 + ....+ ckar-k = f(r)   función matemática discreta

 

donde ci son constantes, es llamada una ecuación de recurrencia de coeficientes constantes de orden k, condicionada a que c0 y ck = 0.

 

Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta definir.

 

El poder de la recursividad es que los procedimientos o conceptos complejos pueden expresarse de una forma simple.

 

Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el punto tanto de partida como de terminación de la definición.

 

Ejemplo:

 

            Base: La secuenciación, iteración condicional y selección son estructuras válidas de control que pueden ser consideradas como enunciados.

 

            Regla recursiva: Las estructuras de control que se pueden formar combinando de manera válida la secuenciación iteración condicional y selección también son válidos.

 

Un conjunto de objetos está definido recursivamente siempre que:

 

            (B) algunos elementos del conjunto se especifican explícitamente

            (R) el resto de los elementos del conjunto se definen en términos de los elementos ya definidos

 

donde

            (B) se llama base

            (R) se llama cláusula recursiva

 

Observaciones:

 

1. El procedimiento se llama a si mismo

2. El problema se resuelve, resolviendo el mismo problema pero de tamaño menor

3. La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzará

 

La recursividad es un método poderoso usado en inteligencia artificial, su poder es que algunos conceptos complejos pueden expresarse en una forma simple. Una definición recursiva difiere de una definición circular en que tiene una forma de escapar de su expansión infinita. Este escape se encuentra en la definición o porción no recursiva o terminal de la definición.

 

Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solución de problemas combinatorios, algunos acertijos, etc.

 

 

Ejemplos:

 

1. Números de Fibonacci

 

Los números de Fibonacci se definen como:

 

            FN = FN-1 + FN-2          para N > 2

            F0 = F1 = 1

 

que definen la secuencia:

 

1,1,2,3,5,8,13,21,34,55,89,144, .....

 

Por ejemplo, si quisiéramos encontrar Fibonacci de 5, entonces:

 

Fibonacci (5) = Fibonacci (4) + Fibonacci (3)

Fibonacci (4) = Fibonacci (3) + Fibonacci (2)

Fibonacci (3) = Fibonacci (2) + Fibonacci (1)

Fibonacci (2) = Fibonacci (1) + Fibonacci (0)

 

De manera iterativa el algoritmo podría ser:

 

estática int Fibonacci (int n)

// versión iterativa

comienza

            fibo [0] ß 1

            fibo [1]ß 1

            para i ß1 hasta n

                        fibo [i] ß fibo [i-1]+ fibo [i-2]

            regresa fibo [n]

termina

 

Resolviendo el mismo problema pero de manera recursiva, obtenemos:

 

estática int Fibonacci (int n)

//versión recursiva

comienza

            si n < 1 entonces

                        regresa 1

            otro

                        regresa Fibonacci (n-1) + Fibonacci (n-2)

termina

 

2. Considere la siguiente ecuación recurrente:

 

            an = an-1 + 2n

            a0 = 1

 

estática int  a (int n)

comienza

            si n = 0 entonces

                        regresa1

            otro

                        regresa 2^n + a (n-1)

termina

 

Los valores de los términos de una sucesión pueden darse de manera explícita mediante fórmulas como:

 

            Sn = n4 - 3n3 - 2n

 

pero también pueden definirse por medio de descripciones que involucren otros términos que les anteceden en la sucesión.

 

por ejemplo:

 

 

estática int suma (int i, int n)

comienza

            si i = n entonces

                        regresa i

            otro

                        regresa n + suma (i,n-1)

termina

 

4. Definición recursiva para elevar un número a una potencia: Un número elevado a la potencia cero produce la unidad; la potencia de un número se obtiene multiplicándolo por sí mismo elevando a la potencia menos uno. Por ejemplo:

 

            32 = 3*(31) = 3*(3*30) = 3*(3*1)= 3*(3) = 9

 

estática int potencia (int n, int k)

comienza

            si k=0 entonces

                        regresa 1

            otro

                        regresa n * potencia (n,k-1)

termina

 

5. Número de Combinaciones

 

Recursivamente, podemos definir el número de combinaciones de m objetos tomados de n, denotado (n,m) para n> 1 y 0 < m < n por:

 

(n,m) = 1                                                       si m = 0 ó m = n ó n = 1

(n,m) = (n-1, m) + (n-1,m-1)                      en otro caso

 

estática int  combinaciones (int n, int m)

comienza

            si m = 0 o m = n o n = 1 entonces

                        regresa 1

            otro

                        regresa combinaciones (n-1,m) + combinaciones (n-1,m-1)

termina

 

6. Algoritmo de Euclides

 

Este algoritmo es considerado el más viejo no trivial.

 

El paso esencial que garantiza la validez del algoritmo consiste en mostrar que el máximo común divisor (mcd) de a y b, (a > b > 0), es igual a a si b es cero, en otro caso es igual al mcd de b y el remanente de a dividido por b, si b > 0.

 

estática int  mcd (int a,b)

comienza

            si b = 0

                        regresa a

            otro

                        regresa mcd (b, a mod b)

termina

 

Ejemplos:

 

mcd (25, 5) = mcd (5,0) = 5

mcd (18,6) = mcd (6,0) = 6

mcd (57, 23) = mcd (23, 1) = mcd (1,0) = 1

mcd (35, 16) = mcd (16,3) = mcd (3, 1) = mcd (1, 0) = 1

 

Definición: Cuando una llamada recursiva es la última posición ejecutada del procedimiento se llama recursividad de cola, recursividad de extremo final o recursión de extremo de cola.

 

Definición: Cuando un procedimiento incluye una llamada a si mismo se conoce como recursión directa.

 

Definición: Cuando un procedimiento llama a otro procedimiento y este causa que el procedimiento original sea invocado, se conoce como recursión indirecta.

 

Al principio algunas personas se sienten un poco incómodas con la recursividad, tal vez porque da la impresión de ser un ciclo infinito, pero en realidad es menos peligrosa una recursión infinita que un ciclo infinito, ya que una recursividad infinita pronto se queda sin espacio y termina el programa, mientras que la iteración infinita puede continuar mientras no se termine en forma manual.

 

Cuando un procedimiento recursivo se llama recursivamente a si mismo varias veces, para cada llamada se crean copias independientes de las variables declaradas en el procedimiento.

 

 

 

 

OTRA FUNCIÓN RECURSIVA:

LA SUMA DE LOS N PRIMEROS NÚMEROS ENTEROS

Con la experiencia adquirida, no tienes ninguna dificultad en desarrollar tu propia función recursiva para hallar la suma de los n primeros números enteros impares. En este caso, la función se puede basar en la fórmula recursiva siguiente:

suma(n) = (2*n−1) + suma(n−1)

Soluciones

Programa en C

Solución comentada al Ejercicio:

/* fichero sum2.c */

#include

void main(void) {

  int n;

  double suma(int);

  printf("Teclea un numero entero positivo: ");

  scanf("%d", &n);

  printf("La suma de los %d primeros impares es %lf ", n, suma(n));

}

double suma(int n) {

  if(n<=1)

      return 1.0;

  return ((2*n-1)+suma(n-1));

}

 

Comentario

Sólo reseñar que no se trata de la suma de los impares hasta el número n que se teclea, sino que es la suma de los n primeros números impares, es decir, si por ejemplo tecleamos 3, el resultado será 9 que es la suma de 1 más 3 más 5.

Obtenido de "http://wwwdi.ujaen.es/~mcdiaz/docencia/ejercicios/wiki/index.php?title=Otra_funci%C3%B3n_recursiva:_La_suma_de_los_N_primeros_n%C3%BAmero_enteros"

 

FUNCIONES PARCIALES RECURSIVAS

Definición de la suma:

  • suma(0,x)=x
  • suma(n+1, x)=succ(suma(n,x))

Definición de la multiplicación:

  • mult(0,x)=0
  • mult(n+1,x)=suma(mult(n,x),x)

Definición de la potencia

  • pot(x,0)=1
  • pot(x,n+1)=mult(pot(x,n),x)

Usamos funciones simples (cero,proyección y succ)

Utilizamos composición y recursión

¿Qué va después de la potencia? La tetración: 3 3=333=327≠(33)3=333333 =39

 

FUNCIONES PRIMITIVAS RECURSIVAS

 

Subconjunto de las funciones recursivas

Siempre son totales

Incluyen las funciones aritméticas más comunes:

  • Suma
  • Resta
  • Multiplicación
  • División
  • Potencia
  • Factorial

Hay funciones totales recursivas que no son primitivas recursivas

  • Argumento diagonal
  • Función de Ackermann

 

Son funciones parciales recursivas:

  • Las funciones básicas:
  •  
    •  
      • Cero

Z(x)=0

  •  
    •  
      • Proyecciones

Ui,n (x1, x2, ..., xn)=xi

  •  
    •  
      • Sucesor

S(x)=x+1

 

Son funciones primitivas recursivas:

Las funciones obtenidas de PR por:

Composición:

h(x1, x2, ..., xn)

g1(x1, x2, ..., xm), g2(x1, x2, ..., xm),..., gn(x1, x2, ..., xm)

f(x1, x2, ..., xm)=h(g1(x1, x2, ..., xm),..., gn(x1, x2, ..., xm))

 

Ejemplo:

f(x)=x+2

h=S

g=S

f(x)=h(g(x))=S(S(x))=x+2

 

Las funciones obtenidas de las anteriores por:

Recursión:

g(x1, x2, ..., xn)

h(x1, x2, ..., xn+2)

f(0,x1, x2, ..., xn)=g(x1, x2, ..., xn)

f(k+1,x1, x2, ..., xn)=h(f(k,x1, x2, ..., xn),k, x1, x2, ..., xn)

Ejemplo (suma):

g(x)=U 1,1(x)=x

h(a,b,c)=S(U1,3(a,b,c))=a+1

f(0,x)=x

f(k+1,x)=h(f(k,x),k,x)=f(k,x)+1

· Ejemplo (factorial):

g=S(0)

h(a,b)=mult(U2,1(a,b),S(U2,2(a,b)))=mult(a,b+1)

f(0)=1

f(k+1)=h(f(k),k)=f(k)*(k+1)

· Ejemplo (predecesor):

g=0

h(a,b)=U2,2(a,b)=b

f(0)=0

f(k+1)=h(f(k),k)=k

· Ejemplo (resta):

     Nótese que x-(k+1)=(x-k)-1

     Calcularemos primero r(k,x)=x-k

g(x)=x

h(a,b,c)=pred(U1,3(a,b,c))

r(0,x)=g(x)=x

r(k+1,x)=h(r(k,x),k,x)=pred(r(k,x))

     Ahora definimos f(a,b)=a-b por composición

f(a,b)=r(U2,2(a,b), U1,2(a,b))=r(b,a)=a-b

 

Todas las funciones PR son totales

Hay funciones computables totales que no son PR

     Argumento diagonal

Enumerar de forma computable las PR: fn(x)

Considerar g(x)= fx(x)+1

Es una función total y computable pero distinta de cada fn

El argumento funciona con cualquier familia computable de funciones totales y computables

     Función de Ackermann

A(0,n)=n+1

A(m,0)=A(m-1,1) si m>0

A(m,n)=A(m-1,A(m,n-1)) si m>0 y n>0

Es claramente una función computable

 

LA FUNCIÓN DE ACKERMANN

 

  • Crece más rápido que cualquier función PR
  • Algunos valores

 

 

 

Una definición alternativa

A(0, n) = n + 1

A(1, n) = 2 + (n + 3) – 3 = n+2

A(2, n) = 2 (n + 3) - 3 = 2n -3

A(3, n) = 2n + 3 - 3

A(4, n) = 22...2 - 3 (n + 3 potencias)

 

A partir de aquí se necesitan nuevas notaciones:

     Flechas de Knuth

     Cadenas de Conway

     Polígonos de Steinhaus y de Moser

 

Una definición alternativa

A(0, n) = n + 1

A(1, n) = 2 + (n + 3) – 3 = n+2

A(2, n) = 2 (n + 3) - 3 = 2n -3

A(3, n) = 2n + 3 - 3

A(4, n) = 22...2 - 3 (n + 3 potencias)

 

A partir de aquí se necesitan nuevas notaciones:

Flechas de Knuth

Cadenas de Conway

Polígonos de Steinhaus y de Moser

 

NUMEROS ENORMES

¿Quién puede nombrar el mayor número? (googol)

El número de granos de arena: Arquímedes (1063)

Partículas en el universo (menor que 1087)

Hay números mucho más grandes

Los números grandes tienen aplicaciones:

     El (primer) número de Skewes: eee79

Aproximadante 10101034

Aparece estudiando la distribución de números primos

     El número de Graham

No puede representarse con notación “normal”

Aparece en el libro Guinness de los Records

Relacionado con la teoría de grafos (teoría de Ramsey)

Números aún más grandes: los del Busy Beaver

     Crecen más rápido que cualquier función computable

 

Pueden ser no totales (parciales)

Incluyen a todas las primitivas recursivas

Equivalen a las while-computables

Se forman a partir de las funciones básicas por

     Composición

     Recursión

     Minimización

Operador de minimización:

     Dada p(y, x1, x2, ..., xn) definimos f(x1, x2, ..., xn)=μy[p(y, x1, x2, ..., xn)=1]

que será el menor y que cumpla la condición (si existe)

 

Ejemplo: la división

También es primitiva recursiva

Necesitaremos funciones auxiliares

     positivo(x)=1 si x>0, 0 si no

     Definición como primitiva recursiva

positivo(0)=0

positivo(x+1)=S(Z(U2,1(positivo(x),x)))=1

     mayor(x,y)=1 si x>y, 0 si no

     Definición como primitiva recursiva

mayor(x,y)=positivo(resta(U2,1(x,y),U2,2(x,y)))

 

·         La división se define como:

Dividendo=cociente * divisor + resto

siendo 0<=resto

Entonces:

Dividendo – cociente * divisor = resto

Dividendo – (cociente+1) * divisor = resto –divisor <0

Dividendo < (cociente+1)*divisor

Por tanto

division(x,y)=μz[mayor((z+1)*y,x)=1]

 

 

Copyright (c)2009 Universidad Mariano Gálvez de Guatemala
Powered by: Best Web Hosting and Affiliate Programs Directory. Created with Free Website Builder