FUNCIONES RECURSIVAS
Se dice que una función es recursiva cuando se define en función de si misma.
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 conducir a bucles infinitos, o a que el programa termine inadecuadamente.
Tampoco todos los lenguajes de programación permiten usar recursividad.
C++ permite la recursividad. 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 de la 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.
Hay algunas limitaciones:
- No es posible calcular el factorial de números negativos, no está definido.
- El factorial de cero es 1.
Por ejemplo:
Podríamos crear una función recursiva para calcular el factorial de un número entero.
El factorial se simboliza como n!, se lee como "n factorial", y la definición es:
n! = n * (n-1) * (n-2) * ... * 1
Ventajas y desventajas de la Recursividad:
Ventajas:
· No es necesario definir la secuencia de pasos exacta para resolver el problema.
· Soluciones simples, claras.
· Soluciones elegantes.
· Soluciones a problemas complejos.
Desventajas:
· Podría ser menos eficiente.
· Sobrecarga asociada con las llamadas a sub algoritmos
· Una simple llamada puede generar un gran número de llamadas Recursivas. (Fact(n) genera n llamadas recursivas)
· El valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fácil solución iterativa.
· La ineficiencia inherente de algunos algoritmos recursivos.
Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una
secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia
no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al
menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de
llamadas recursivas.
Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición
recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna
manipulación de uno o casos más simples no recursivos.
Ejercicio #1: Factorial de un número
#include <iostream>
using namespace std;
long double factorial(int);
int main()
{ int n;
cout << "Introduzca numero: ";
cin >> n;
cout << "factorial: " << factorial(n) << endl;
system("pause");
}
long double factorial(int n)
{
long double fact;
if (n==0)
return 1;
else
return n*factorial(n-1);
}
Ejercicio #2: Las Torres De Hanoi
# include <iostream>
using namespace::std;
// FUNCION MOVER_TORRES
void Mover_Torres(int N, int Origen, int Intermedio, int Destino)
{ // Abre funcion Mover_Torres
if (N > 1)
{ // Abre if
Mover_Torres(N - 1, Origen, Destino, Intermedio);
/* Se mueve una torre de N - 1 discos desde la columna origen
pero hacia la columna intermedia ( para dejar la destino libre)
usando la columna destino como intermedia cout << "\nMueve disco "
<< N << " de " << Origen << " a " << Destino <<endl;
con esta instrucción se mueve el disco de la base hacia su destino
Como comento arriba, ahora hay que mover nuevamente la torre de
N - 1 discos hacia el destino original ( en donde se ha puesto el
disco mayor ) Esto implica una segunda llamada recursiva. Ahora
el origen es la columna intermedia a la que se movió la torre y
el destino es el destino primitivo,lo que originalmente era el
origen se usa ahora como columna intermedia */
cout << "\nMueve el disco " << N << " de " << Origen << " a " << Destino << endl;
Mover_Torres(N - 1, Intermedio, Origen, Destino);
} // Cierra if
// El caso limite mas sencillo se resuelve directamente
if (1 == N)
cout << "\nMueve el disco 1 de " << Origen << " a " << Destino << endl;
} // Cierra funcion Mover_Torres
int main()
{ // Abre funcion main
int Discos;
cout << "\nEste programa resuelve el problema clasico de las Torres de Hanoi";
cout << " mediante la recursion." << endl;
cout << "\nPor favor introduzca el numero de discos que quiere mover ";
cout << " de la pila 1 a la pila 3" << endl;
cin >> Discos;
Mover_Torres(Discos, 1, 2, 3);
cout << endl << endl;
return 0;
system("pause");
} // Cierra funcion main
Ejercicio: Multiplicar dos números
#include <iostream>
using namespace std;
int producto(int, int);
int main()
{
int n1,n2,p;
cout << "Introduzca primer numero: ";
cin >> n1;
cout << "Introduzca segundo numero: ";
cin >> n2;
p=producto(n1,n2);
cout << "producto: " << p << endl;
system("pause");
}
int producto(int a, int b)
{
if(a==0 or b==0)
return 0;
else
{
return a+producto(a,b-1);
}
}
Gracias
Jossua Orellana G, Marcelo Olalla.