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 candidato 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

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:

c_oa_r +c₁a_r-1 + c₂a_r-2 + ....+ c_ka_r-k = f(r)   función matemática discreta

donde c_i son constantes, es llamada una ecuación de recurrencia de coeficientes constantes de orden k, condicionada a que c₀ y c_k = 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.

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:

            3² = 3*(3¹) = 3*(3*3⁰) = 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

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.

ALGORITMOS RECURSIVOS

 

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

Recursividad indirecta

Cuando en una subrutina hay llamadas a ella misma se habla de recursividad directa, en contraposición, cuando se tienen varias subrutinas y estas se llaman unas a otras formando ciclos se dice que la recursión es indirecta.

Ejemplo:

1.-Da un algoritmo recursivo para hallar an, donde a es el número real distinto de cero y n un entero no negativo.

Solución:Podemos construir un algoritmo recursivo basándonos en la definición recursiva de an. 

Esta definición afirma que an+1 = a.an para n > 0 con la condición inicial a0 =

1. Para calcular an podemos usar sucesivamente la regla recursiva para reducir el exponente hasta que se haga cero

Algoritmo 1 un algoritmo recursivo para hallar an

Procedure potencia (a número real no nulo, n: entero no negativo) If n = 0 the potencia (a,n):=1 Else potencia (a,n):=a.potencia (a,n-1)

2.-Da un algoritmo recursivo para calcular el máximo común divisor de dos enteros no negativos a y b, a > b.

Solución: nos podemos basar en la reducción mcd(a, b) = mcd (b mod a, a) y la condición mcd (0,b) = b cuando b > 0.

Algoritmo 2 un algoritmo recursivo para hallar el mcd (a, b)

Procedure mcd(a, b: entero no negativo, a<b) If a = 0 the mcd (a,b):=b Else mcd (a, b):=mcd (b mod a,a)

 

3.- Expresa el algoritmo de búsqueda lineal como procedimiento recursivo

Solución: para buscar x en la sucesión a1, a2 …an en el paso decimo comparamos x y ai. Si x = a entonces i es la posición de x. es el caso contrario la búsqueda de x se reduce a buscar en la sucesión con un elemento menos es decir la sucesión ai + 1, …..an.

Algoritmo 3 un algoritmo recursivo de búsqueda lineal

Procedure búsqueda (i, j, x) If ai = x the Posicion :=i Else if i = j the Posicion :=0 Else busqueda (i+ 1, j, x

4.- El procedimiento recursivo del algoritmo 4 de el valor de n! cuando la entrada en un entero positivo n

Algoritmo 4 un algoritmo recursivo para la función factorial

Procedure factorial (n: entero positivo) If n= 1 the Factorial (n) :=1 Else factorial (n) :n. factorial (n-1)

5.-

Algoritmo 5 un algoritmo recursivo para los números de fibonacci

Procedure fibonacci (n entero no negativo) If n= 0 the Fibonacci (0) = 0 Else if n = 1 the Fibonacci(1) = 1 Else Fibonacci (n) = Fibonacci (n-1)+ Fibonacci (n-2)

 

Un algoritmo se llama recursivo si resuelve un problema reduciéndolo a un caso del mismo problema con cada dato de entrada más pequeño

Funciones

Los números de fabanacci, f0, f1, f2…. De definen a partir de las ecuaciones f0 = 0, f1 = 1 y fn = fn-1 + f n-2

Para n = 2, 3, 4, ….