RECURSIVIDAD EN C++

PROGRAMACION ESTRUCTURADA



RECURSIVIDAD EN C++



OSCAR JOSUE MONTUFAR SUAZO



UNIVERSIDAD TECNOLOGICA DE HONDURAS
FACULTAD: INGENIERIA EN COMPUTACION
INGENIERIA EN COMPUTACION
EL PROGRESO, YORO
2015
Índic

Objetivo general 3
Introducción 4
Recursividad en C++ 5
Función recursiva para cálculo de factoriales 6
Principios de la recursividad: 7
Ventajas y desventajas de la Recursividad: 8Ventajas: 8
Desventajas: 8
Ejemplos de funciones recursivas en C++: 9
Suma recursiva de los elementos de un vector 10
Buscar el máximo de un vector (I) 10
Búsqueda lineal recursiva (con dos casos base) 11
Función de partición 11
Torres de Hanói 13
Visualizar las permutaciones de n elementos. 15
Búsqueda binaria 16
Función de búsqueda binaria: 17
Algoritmo de Euclides 17
Bibliografía 19
Recomendaciones20







Objetivo general

Conocer y entender el concepto y la función especifica de la recursividad en C++.




































Introducción

Identificamos la recursividad como una alternativa a utilizar como, a la iteración. La recursividad es una herramienta poderosa e importante en la resolución de problemas en programación. Una solución recursiva es normalmente menoseficiente en términos de tiempo de computadora que una solución iterativa debido a las operaciones auxiliares que llevan consigo las llamadas suplementarias a las funciones: sin embargo, en muchas circunstancias el uso de la recursión permite a los programadores especificar las soluciones naturales, más lógicas, elegantes, sencillas, que serían, en caso contrario difícil de resolver.Recursividad en C++

La recursividad es una técnica de programación elemental que permite que una función pueda llamarse asimismo desde la misma función. Se puede utilizar la recursividad como una alternativa a la iteración (blogspot.com, 2015)

No todas las funciones pueden llamarse a sí mismas, sino que deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducira bucles infinitos, o a que el programa termine inadecuadamente. Tampoco todos los lenguajes de programación permiten usar recursividad. C++ permite la recursividad. (blogspot.com, 2015)

Cada vez que se llama a una función, se crea un juego de variables locales, de este modo, si la función hace una llamada a sí misma, se guardan sus variables y parámetros, usando la pila, y la nueva instancia dela función trabajará con su propia copia de las variables locales. Cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila y continúa la ejecución en el punto en que había sido llamada. (blogspot.com, 2015)

Por ejemplo para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La funciónque se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad. (blogspot.com, 2015)
De esta forma podríamos crear una función  recursiva para calcular el factorial de un número entero. (blogspot.com, 2015)

El  factorial se simboliza como n!,se lee como "n factorial", y la definición es:

n! = n * (n-1) * (n-2) * ... * 1

Hay algunas limitaciones:

No es posible calcular el factorial de números negativos, no está definido. (blogspot.com, 2015)



El factorial de cero es 1.

De modo que una función bien hecha para cálculo de factoriales debería incluir un control para esos casos:

Función recursiva para cálculo de factoriales
intfactorial(int n) {
 if(n < 0) return 0;
 else
 if(n > 1) return n*factorial(n-1); /* Recursividad */
 return 1; /* Condición de terminación, n == 1 */
} (blogspot.com, 2015)

Veamos paso a paso, lo que pasa cuando se ejecuta esta función, por ejemplo: factorial (4):
1aInstancia 
n=4 
n>1 
salida ← 4 * factorial (3) (Guarda el valor de n = 4)
2aInstancia 
n>1 
salida ← 3*factorial (2) (Guarda el valor...