ZZ
Dirección
General de Educación Superior Tecnológica
INSTITUTO TECNOLÓGICO DE SALINA CRUZ
TEMA:
Investigación “recursividad”
FACILITADOR:
Susana Monica Roman najera
NOMBRE:
Asignatura:
Estructuras y
organización de datos
SEMESTRE:
3RO GRUPO: 3E
CARRERA: ING. EN TEC. DE LA INFORMACION Y
COMUNICACIÓN.
Recursividad
Primero debemos decir
que la recursividad no es una estructura de datos, sino que es una técnica de
programación que nos permite que un bloque de instrucciones se ejecute n veces.
Remplaza en ocasiones a estructuras repetitivas.
Este concepto será de
gran utilidad para el capítulo de la estructura de datos tipo árbol.
La recursividad es un
concepto difícil de entender en principio, pero luego de analizar diferentes
problemas aparecen puntos comunes.
En Java los métodos
pueden llamarse a sí mismos. Si dentro de un método existe la llamada a sí
mismo decimos que el método es recursivo.
Cuando un método se
llama a sí mismo, se asigna espacio en la pila para las nuevas variables
locales y parámetros.
Al volver de una llamada
recursiva, se recuperan de la pila las variables locales y los parámetros
antiguos y la ejecución se reanuda en el punto de la llamada al método. Recursión es una
técnica de programación en el cual un método puede llamarse a sí mismo. La recursión es muy interesante
y una técnica efectiva en programación ya que puede producir algoritmos cortos
y eficientes.
Algo es recursivo si se define en términos de sí mismo
(cuando para definirse hace mención a sí mismo).
Si la invocación de un subprograma (función o subrutina) se
produce desde el propio subprograma se dice que se trata de un subprograma
recursivo.
Un método recursivo es un método, directa o indirectamente,
se hace una llamada a sí mismo.
La recursión consiste en el uso de métodos recursivos.
Procedimientos
recursivos
Los
procedimientos recursivos o recurrentes se pueden clasificar en dos formas
distintas:
- Recursividad
directa o
- Recursividad
indirecta
La recursividad
directa se presenta cuando el método se manda llamar a sí mismo dentro
de su propio cuerpo de instrucciones.
public int Metodo(int n)
{
:
n
= Metodo(n-1);
}
La recursividad
indirecta se manifiesta cundo un método llama a otro y dentro del
segundo se manda llamar al primero. O cuando existe la llamada a métodos de
forma encadenada y al terminar el último método llamado, transfiere el control
al anterior, hasta llegar al método que inicio la serie de llamadas.
public int Metodo1(int n)
{
:
n
= Metodo2(n-1);
}
public int Metodo2(int n)
{
:
n
= Metodo1(n-1);
}
Analizando
el concepto de recursividad y su clasificación, puede indicar que es
un procedimiento infinito, que solo se detendrá en el momento que se agote la
memoria, generando un error de programación y la interrupción del mismo.
Pero
esto no es así, ya que debe existir un elemento que indica el retorno de un
resultado concreto y no el retorno de la llamada al método recursivo o
recurrente.
Forma
de generar la recursividad
Un problema clásico:
El factorial de un número.
Todos conocemos que
la definición matemática del factorial de un número n se obtiene de la
siguiente forma:
n! = 1*2*3*.......*n
ó n! = n*(n-1)*(n-2)*.....1
Por definición
matemática, también sabemos que:
0! = 1
Con lo que tendríamos
la siguiente definición de factorial:
|
n!
|
1
|
Si n=0
|
Caso Base
|
|
n*(n-1)
|
Otros casos
|
Parte Recursiva
|
Un problema que
puede resolverse de manera recursiva, debe tener por lo menos caso base y 1
parte recursiva, sino no hay recursión.
Ahora,
para implementarlo en un lenguaje de programación como Java, solo tenemos que
traducir nuestros casos bases y partes recursivas:
Funcionamiento del proceso
|
n
|
Llamado a factorial
|
|
4
|
4*factorial(3)
|
|
3
|
3*factorial(2)
|
|
2
|
2*factorial(1)
|
|
1
|
1*factorial(0)
|
|
0
|
1
|
En
general el proceso es (4*factorial(3*factorial(2*factorial(1*factorial(0)))))
Realizar
de manera recursiva la sumatoria de n números naturales de manera recursiva.
La
sumatoria de n números se realiza de la siguiente forma:
n=10
1+2+3+4+5+6+7+8+9+10
= 10+9+8+7+6+5+4+3+2+1
De
tal forma que podemos determinar que:
1 si
n = 1 paso
básico
n +
(n-1) si
n > 1 paso
inductivo o proceso recursivo
//5+suma(4+suma(3+suma(2+suma(1))))
Imprimir
de manera recursiva la serie de fibonnaci
La serie de fibonacci
trabaja de la siguiente forma:
Paso 1: Si tenemos
dos semillas formadas por s1=0 y s1=1
0 1
Paso 2. Se suman para
obtener el resultado
0 1 1
Ahora la semilla 1 se
queda con el valor de la semilla 2 y el resultado se asigna a la semilla 2 y se
vuelve a realizar el paso 2. De tal forma que la serie queda de la
siguiente forma:
0 1 1 2 3 5 8 13 21
34 55 89 ………….
Fibonnacci de manera
recursiva
Fibonacci(0,1,21)=1
Fibonacci(1,1,21)=2
Fibonacci(1,2,21)=3
Fibonacci(2,3,21)=5
Fibonacci(3,5,21)=8
Fibonacci(5,8,21)=13
Fibonacci(8,13,21)=21
Realizar
de manera recursiva la potencia de un número para n.
El
cálculo de la potencia de un número se resuelve de la siguiente manera.
Xp=X*X(p-1)*X(p-2)*X(p-3)……=
25= 2 * 2 * 2 * 2 * 2
Sabemos
que 20= 1 por lo que determinamos
1 si
p = 0 paso
básico
n *
(n,
p-1) si
p > 0 paso
inductivo
24 2*potencia(2*potencia(2*potencia(2*potencia(2,0))
Potencia(2,4)=2*potencia(2,3)=16
Potencia(2,3)=2*potencia(2,2)=8
Potencia(2,2)=2*potencia(2,1)=4
Potencia(2,1)=2*potencia(2,0)=2
Potencia(2,0)=1
Realizar
el producto de un número por sumas sucesivas de manera recursiva.
El
producto de un número (3*9) se realiza de la siguiente forma:
1 2 3 4 5 6 7 8 9
3+3+3+3+3+3+3+3+3
cant
=0 0 caso
base
n+(cant-1) proceso
recursivo
Realizar
de manera recursiva como calcular un número en binario a través de
desplazamientos sucesivos
La
manera de convertir a binario un número es de la siguiente forma:
Si es
para un número de ocho bits el rango de valores abarca de 0 a 255, si es en ese
caso se debe de utilizar una máscara de 0x80. Que representa a un
número en binario 10000000 es decir el último bit en 1.
Se
realiza una operación (AND)& a nivel de bits del número a convertir y si el
resultado es cero entonces ese representa al primer valor del número en binario
y si no es cero entonces este lo representa.
Posterior
a esto se desplaza el bit una posición a la derecha y se vuelve a hacer la
misma operación & y nos vuelve a dar como resultado 0 o un numero diferente
de 0.
Este
proceso se repite hasta que se llegue hasta el final # de bits. En este caso 8
iteraciones.
Ejemplo:
Numero
a convertir es 13
La
máscara es 0x80=10000000
13
en binario es 00001101
La
máscara es 10000000
Resultado & 00000000 da
el primer valor del número convertido 0
Se
repite el mismo proceso pero con el bit 1 de la máscara recorrido una posición
a la derecha.
13
en binario es 00001101
La
máscara es 01000000
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00100000
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00010000
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00001000
Resultado & 00001000 da
el primer valor del número convertido 1
13
en binario es 00001101
La
máscara es 00000100
Resultado & 00000100 da
el primer valor del número convertido 1
13
en binario es 00001101
La
máscara es 00000010
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00000001
Resultado & 00000000 da
el primer valor del número convertido 1
No hay comentarios:
Publicar un comentario