Recursividad
Una función es recursiva cuando se define en función de si misma, pero no todas la funciones pueden llamarse a si mismas. 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.
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 si 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 continua la ejecución en el punto en que había sido llamada.
Por ejemplo:
Prodrí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:
#e3e3e3;”>n! = n * (n-1) * (n-2) * … * 1
Para este ejemplo no es posible calcular el factorial de números negativos, no está definido.
Debemos de tomar en cuenta que 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:
#e3e3e3;">/* Función recursiva para cálculo de factoriales */
#aa4400; font-weight: bold;">int factorial(#aa4400; font-weight: bold;">int n) {
#aa4400; font-weight: bold;">if(n #aa4400; font-weight: bold;">return 0;
#aa4400; font-weight: bold;">else #aa4400; font-weight: bold;">if(n > 1) #aa4400; font-weight: bold;">return n*factorial(n-1); /* Recursividad */
#aa4400; font-weight: bold;">return 1; /* Condición de terminación, n == 1 */
}
La recursividad consume muchos recursos de memoria y tiempo de ejecución, y se debe aplicar a funciones que realmente le saquen partido.
También existen otras formas de implementar algoritmos recursivos, por lo que no es necesario que una función se invoque a si misma.
Ejemplo: un par de funciones A y B pueden crear un algoritmo recursivo si la función A invoca a la función B, y esta a su vez invoca a la función A.
Veamos un ejemplo. Partamos de la siguiente serie:
#e3e3e3;">1 - 1/2 + 1/3 - 1/4 + 1/5 - ... - 1/2*n + 1/2*n+1 - ...
Aqui tenemos otro ejemplo aun mas complejo:
#include
using namespace std;
double par(int);
double impar(int);
double suma(int);
int main() {
cout
cout
cout
cout
cout
cout
return 0;
}
double suma(int n) {
if(n % 2) return impar(n);
else return par(n);
}
double par(int n) {
return impar(n-1)-1/double(n);
}
double impar(int n) {
if(n == 1) return 1;
return par(n-1)+1/double(n);
}
Referencias: http://c.conclase.net/curso/?cap=024
#Mastery21 #TC1017
