Recursividad

------Recursividad--------

Es la capacidad o funcion o procedimiento de un metodo de invocarse a si mismo durante la ejecucion de un programa. Una funcion o procedimiento es recursivo cuando esta definido en funcion de si mismo.

Ejemplo: funcion factorial. Dado un entero positivo llamado n se define su factorial como el producto de todos los enteros entre n y uno.

5!=5*4*3*2*1=120

a) Algoritmo de la funcion factorial.

funcion FACTORIAL(n)

inicio
si n=0 entonces
FACTORIAL=1
sino
FACTORIAL=N*FACTORIAL(n-1)
fin_si
fin_funcion

b) Secuencia de fibbonachi es aquella secuencia de enteros donde cada elemento es la suma de los 2 anteriores. 0,1,1,2,3,5,8,13,21

=definicion recursiva=

if n==0 orh==1 entonces fib(n)=n
if n>=2 entonces fib(n)=fib=(n-2)+fib(n+1)//llamado recursividad

algoritmo.
funcion FIB(n)
Inicio
SI N==0 O N==1 entonces
FIB=n
sino
FIB(n-2)+FIB(n-1)
fin_si
fin_funcion

Ejemplo:

n=2

fib(2)=fib(2-2)+fib(2-1)
=fib(0)+fib(1)
=0+1=1

PROCEDIMIENTOS RECURSIVOS
1.- Funcion factorial
2.- Secuencia de fibbonacci
3.- Torres de hanoi
4.- Busqueda binaria


c) Torres de hanoi

Se tienen 3 torres de n discos de diferentes tamaños. Inicialemente los discos estan ordenados del mayor al menor en la primer torre. El problema consiste en pasar los discos a la tercer torre utilizando la segunda como auxiliar.
Reglas:
1.-En cada movimiento solo pueden mover un disco.
2.-No puede quedar un disco mayor sobre uno menor.


Procedimiento Hanoi(N, ORIGEN, AUXILIAR, DESTINO)
si N=1 entonces
Escribir "Mover un disco de ",ORIGEN,"a",DESTINO
sino
Regresar Hanoi(N-1, ORIGEN,DESTINO,AUXILIAR)//llamada recursiva
Escribir "Mover un disco de", ORIGEN, "a", DESTINO
Regresar Hanoi(N-1, AUXILIAR, ORIGEN,DESTINO)//LLAMADA RECURSIVA
fin_si
fin_procedimineto

NOTA: poner contador para que nos diga cuantos movimientos fueron.

d)busqueda binaria: considere un arreglo de elementos en el cual los objetos se han colocado en cierto orden. Al aplicarle la busqueda en este arreglo, primero compara el elemento que se busca en el que se encuentra en el centro del arreglo. Si son iguales la busqueda termina con exito, sino, si el elemento de en medio es mayor que el que se busca, el proceso de busqueda se repite en la 1er mitad del arreglo, sino, el proceso se repite en la segunda mitad del arreglo.

=algoritmo recursivo de buskeda binaria=
1.- if(low>high)
return -1//no se encontro el elemento x
2.- else mid=(low+high)/2
"3.- if(x==a[mid]) //mid=7/2=3 //5=a[3],5=5"
return (mid) //localizo elemento en la posicion mitad
"4.- else if(x"5.- busqueda(x, a[low], a[mid-1]) //low=0, 3-1, //llamada recursiva"
"6.- else busqueda(x, a[mid+1],a[high]) //a[3+2], a[7] //llamada recursiva"

Ejemplo:

(low)0 1 2 3 4 5 6 7(high)
" a={1,3,4,5,17,18,31,33} "
1ra mitad mid 2da mitad
1ra vez low=0
high=7
x=? 5