Recursivisas

Se dice que una función es recursiva cuando se define en función de si misma.
No todas la funciones pueden llamarse a si 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 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 laejecució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:
n! = n * (n-1) * (n-2) * ... * 1
Hay algunas limitaciones:
* No es posible calcular el factorial de números negativos, no está definido.
* El factorial de ceroes 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 */
int factorial(int n) {
if(n < 0) return 0;
else if(n > 1) return n*factorial(n-1); /* Recursividad */
return 1; /* Condición determinación, n == 1 */
}
Veamos paso a paso, lo que pasa cuando se ejecuta esta función, por ejemplo: factorial(4):
1a Instancia
n=4
n > 1
salida ← 4 * factorial(3) (Guarda el valor de n = 4)
2a Instancia
n > 1
salida ← 3*factorial(2) (Guarda el valor de n = 3)
3a Instancia
n > 1
salida ← 2*factorial(1) (Guarda el valor de n = 2)
4a Instancia
n == 1 →retorna 1
3a Instancia
(recupera n=2 de la pila) retorna 1*2=2
2a instancia
(recupera n=3 de la pila) retorna 2*3=6
1a instancia
(recupera n=4 de la pila) retorna 6*4=24
Valor de retorno → 24
Aunque la función factorial es un buen ejemplo para demostrar cómo funciona una función recursiva, la recursividad no es un buen modo de resolver esta función, que sería más sencilla y rápida con unsimple bucle for.
La recursividad consume muchos recursos de memoria y tiempo de ejecución, y se debe aplicar a funciones que realmente le saquen partido.
Veamos otro ejemplo: visualizar las permutaciones de n elementos.
Las permutaciones de un conjunto son las diferentes maneras de colocar sus elementos, usando todos ellos y sin repetir ninguno. Por ejemplo para A, B, C, tenemos: ABC, ACB,BAC, BCA, CAB, CBA.
#include <iostream>
using namespace std;

/* Prototipo de función */
void Permutaciones(char *, int l=0);

int main(int argc, char *argv[]) {
char palabra[] = "ABCDE";

Permutaciones(palabra);cin.get();
return 0;
}

void Permutaciones(char * cad, int l) {
char c; /* variable auxiliar para intercambio */
int i, j; /* variables para bucles */
int n = strlen(cad);

for(i = 0; i <n-l; i++) {
if(n-l > 2) Permutaciones(cad, l+1);
else cout << cad << ", ";
/* Intercambio de posiciones */
c = cad[l];
cad[l] = cad[l+i+1];
cad[l+i+1] = c;
if(l+i == n-1) {
for(j = l; j < n;...