Funciones recursivas

FUNCIONES RECURSIVAS

Las funciones en matematicas son la relacion que existen entre un conjunto y otroPara todo valor en un dominio A existe un unico valor en el contradominio o conjunto B

El grafico muestra una function compuesta ya que esta conformada por condiciones.Si x=0 entonces su imagen =0 de lo contrario su imagen =1Si f(2) 2 no es igual a 0 por lo tanto f(2)=1f(0)=?


Ahora veamos otra funcion un poco mas compleja

Si buscamos la imagen de 0 entonces su imagen =1Que pasa con f(6)Cumple con la regla pero vemos que la imagen llama nuevamente a la funcion

Busquemos cual es la imagen de f(6)

f(6)=?F(6)=6*f(5)……Realizar el procedimiento:

El procedimiento ejecutado es un procedimiento recursivo porque recurre a utilizar la misma funcion para encontrar el valor de la imagen entonces para buscar x yo llamo a la function n veces y llegamos a un punto donde ya no se llama a la funcion y este el el punto de control para no volver a llamar a la funcion.

U2. Recursividad.

2.1. DefiniciónUn método recursivo es un método que se llama así mismo, ya sea directa o

indirectamente, a través de otro método.(Deitel, H. M. & Deitel P. J., 2004)

Un método parcialmente definido en términos de sí mismo, ya sea directa o indirectamente, a través de otro método.

(Weiss, M. A)

U2. Recursividad.

2.1. Definición

Caso base

Parte recursiva

SI

NO

U2. Recursividad.

• TIPOS:• Recursión simple• Recursión múltiple• Recursión cruzada o indirecta• Recursión anidada

2.2. Procedimientos Recursivos

U2. Recursividad.

• FACTORIAL• ¿Cómo se calcula el factorial de un número?

• Ejemplo: • 0!, 1!, 2!, 3!, 4!, 5!

2.3. Ejemplo de Casos

U2. Recursividad.

• Factorial (forma iterativa)

-- Caso Basefactorial = 1;

-- Parte Recursiva for (int i =n; i >= 1; i --)

factorial *= i;

factorial *= i

SI

i = n i >= 1 i --

n

factorial =1

Ejemplo de Casos

U2. Recursividad.

• Factorial (forma recursiva)int factorial (int n){ if (n <= 1)

return 1; else

return (n * factorial ( n-1 ));}

n <= 1 return 1

return(n * factorial (n-1))

SI

NO

n

2.3. Ejemplo de CasosEjemplo de Casos


N es 3

FACTORIAL 3* FACTORIAL (2)

Retorno 6

N es 2


Retorno 2

N es 1


Retorno 1

N es 0

FACTORIAL 1

Retorno 1

FACT FACTORIAL (3)

Ciclo del Factorial Recursivo

FUNCIONES RECURSIVAS vs FUNCIONES ESTANDAR

DE FORMA RECURSIVA SE ALMACENA UNA GRAN CANTIDAD DE DATOS DE MANERA ESTANDAR UTILIZO 2 VARIABLESEL PROCESO ES MUCHO MAS LENTO EN LA RECURSIVDAD POR LO QUE TENGO QUE ESTAR GUARDANDO Y SACANDO DE LA PILA Y LLAMANDO A LA FUNCION POR LO QUE:NO SIEMPRE VA HACER LA MEJOR SOLUCION VAMOS A DECIR QUE ES LA ULTIMA SOLUCION QUE VAMOS A UTILIZAR

U2. Recursividad.

Ejercicio• Encuentre el error en el siguiente método recursivo y explique cómo corregirlo:

int suma(int n){

if (n == 0)return 0;

elsereturn n + suma (n);

}

Definición- Es una Técnica que

permite que una función se llame a si misma.

Recursividad

Definition- Un algoritmo es recursivo si al estar encapsulado en una función es llamado desde la misma función por lo menos 1 vez.

Recursión va ligado a repetición

1.1 Validez del algoritmo recursivo

Caso Base• Evita que el

algoritmo sea infinito.

• El problema puede resolverse sin tener que hacer uso una nueva llamada a si mismo.

Al menos 2 elementos

Paso Recursivo Relaciona el resultado

del algoritmo en base a los resultados de casos mas simples.

Se hacen llamadas a la misma función pero cada vez mas próximas al caso base.

¿Cuándo usar recursividad?

Es una técnica potente de programación que permite resolver problemas

complejos en forma simple elegante y clara.

Sin Embargo: Sera la ultima solución a intentar en caso que los procesos iterativos

no funcionen.

El uso de recursividad únicamente cuando no haya solución iterativa.

Si analizamos en el caso factorial Por Recursividad: Se tiene que almacenar datos y direcciones en la

pila del programa. Por Iteración: se almacenan 2 datos nada mas.

Existen algoritmos complejos se codifican mas fácil mediante métodos recursivos.

RECURSIVO:

Int Factorial (int n ){If (n==0) return (1);Return (n*Factorial (n-1));}

ITERATIVO:

Int Factorial (int n ){Int ¡, res = 1;For(¡=1;¡<=n;¡++ ) res = res*¡;return (res);}

Estrategias para procesosRecursivos

• Dos estrategias de resolución de problemas recursivos:• Divide y vencerás : Divide el problema de tamaño n en problemas más pequeños cada uno de

los cuales es similar al original pero de menor tamaño. • Si se llega a una solución de los sub-problemas, se podrá construir de forma sencilla una solución al

problema general. • Cada uno de esos sub-problemas se podrá resolver de forma directa (caso base) o dividiéndolos en

problemas más pequeños mediante la recursividad.

• Backtracking = Fuerza Bruta = Vuelta Atras. Divide la solución en pasos, en cada uno de los cuales hay una serie de opciones que ha que probar de forma sistemática. En cada paso se busca una posibilidad o solución o solución aceptable.• Si se encuentra se una solución valida pasa a decidir el paso siguiente.• Si no se encuentra una solución aceptable, se retrocede hasta la última solución aceptable

encontrada y se elige una opción distinta a la anterior. La recursividad se utiliza para poder retroceder hasta encontrar una solución aceptable.

• Ejemplos: Juegos de tablero, laberintos, etc.

3.1 Definición de Procesos Recursivos

1. ¿Cuál es la variable de recursión? Es lo primero que hay que identificar Indica cuantas veces se repite la acción principal del proceso.

2. ¿Cuál es el dominio de la variable de recursión?• El conjunto de números naturales de 0 a N.

3. Caso Base Resolver el problema para el primer valor del dominio de la variable de recursión (Definido en el Paso 2)

4. Paso Recursivo Si ya existe un proceso que hace lo que se necesita, en este paso se lo LLAMA disminuyendo o aumentado el numero de elementos N para que se acerque al CASO BASE. Este paso debe completar lo que falte.

3.2 Resolución de Procesos Recursivos

Resolución de problemas recursivos. Para hallar la solución recursiva a un problema podemos hacernos tres preguntas:

1. ¿Cómo se puede definir el problema en términos de uno o más ?• Problemas más pequeños del mismo tipo que el original.

2. ¿Qué instancias del problema harán de caso base?• Conforme el problema se reduce de tamaño, se alcanzará el caso base

3. ¿Cómo se usa la solución del caso base para construir una solución• Alcanzado el caso base, determinar como ahora lograr la solución

final.

3.3 Pasos para crear un AR Escriba un «IF»

a. caso Base Donde la función no se llama a si misma.Simple = No se necesita llamada recursiva (no hay repetición) Tal vez deba almacenar el resultado en una variable.

Escriba un «ELSE»

b. Paso Recursivo Donde la función se llama a si mismaEs la próxima entrada/estado

Esta deberá aproximarse cada vez mas al caso base

Asuma que la llamada recursiva funciona:

a. Pregúntese que hace el algoritmo?

b. Pregúntese como ayuda en la solución del problema ?

3.1.4 Base Para escribir el AR IF (pregunta por el caso base) { //Caso Base

} else {

// Paso Recursivo

}

U2. Recursividad.

Práctica (Equipo)• De los siguientes problemas resueltos de forma iterativa, encontrar su solución

recursiva mediante codificación:1. Fibonacci (n-1) + (n-2)2. Conversión de un número decimal a binario (n/2, n%2)3. Potencia (base, exponente)

U2. Recursividad.

Práctica (Equipo)Fibonacci

int Fibonacci (int n){//Casos Baseif (n == 0)

return 0;else{

if (n == 1)return 1;

// Paso recursivoelse{

return Fibonacci(n-1)+Fibonacci(n-2);}

}}

U2. Recursividad.

Práctica (Equipo)Conversión Decimal a Binario

void aBinario (int n){// Paso recursivoif (n >= 2)

aBinario (n/2);System.out.print(n%2);

}

U2. Recursividad.

Práctica (Equipo)Elevar a una potencia

int Potencia (int n, int exp){//Casos Baseif (exp == 0)

return 1;else{

if (exp == 1)return n;

// Paso recursivoelse{

return n * Potencia(n, exp-1);}

}}

U2. Recursividad.

Recursividad & IteraciónRECURSIVIDAD• Llamadas repetidas a los métodos.• Termina cuando se reconoce un caso base.• Se aproxima poco a poco a la terminación.• Infinita cuando no reduce el problema.• Sobrecarga de llamadas a métodos.

ITERACIÓN• Instrucción de repetición explícita.• Termina cuando falla la condición.• Repetición controlada por contador.• Infinita cuando la condición nunca se vuelve

falsa.

U2. Recursividad.

Ventajas• Menos líneas de código.• Refleja el problema con más naturalidad.• Produce un programa más fácil de entender y depurar.

U2. Recursividad.

Desventajas• Tiempo de procesador.• Espacio en memoria, consume memoria adicional.

Programación en C 30

CONCLUSIONES

Programación en C 31

Ejemplos de funciones recursivas en C++:

#include <iostream>#include <stdio.h>using namespace std;int par(int num);int impar(int num);main(){ int num; cout<<"Ingrese un numero"<<endl; cin>>num; if(par(num)) { cout<<"es par"; } else cout<<"Es impar";}int par(int num){ if(num==0) return(1); else return impar(num-1); }int impar(int num){ if(num==0) return 0; else return par(num-1);}

Construya un programar recursivo para indicar si un numero es par o impar

Education

Funciones recursivas