Recursividad
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, 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. Cuando se llama a una función, se crea un nuevo juego de variables locales, de este modo, si la función hace una llamada a si misma, se guardan sus variables y parámetros en 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.
La recursividad es otra de esas tecnicas de programación que cuando las vemos por vez primera parecen muy intimidantes pero en el siguiente ejemplo descubriremos el misterio en un programa muy simple pero para propósitos de ilustración resulta excelente.


# include  /* Contiene el prototipo para printf */

void count_dn(int count) ; /* Prototipo para count_dn */
int main( )
{
    int index ;
    index = 8 ;
    count_dn(index) ;
    return 0 ;
}

void count_dn(int count)
{
    count -- ;
    printf ( "El valor de la cuenta es %d\n", count ) ;
    if (count > 0)
    count_dn(count) ;
    printf ( "Ahora la cuenta es %d\n", count ) ;
}


/* Resultado de la ejecución:
El valor de la cuenta es 7
El valor de la cuenta es 6
El valor de la cuenta es 5
El valor de la cuenta es 4
El valor de la cuenta es 3
El valor de la cuenta es 2
El valor de la cuenta es 1
El valor de la cuenta es 0
Ahora la cuenta es 0
Ahora la cuenta es 1
Ahora la cuenta es 2
Ahora la cuenta es 3
Ahora la cuenta es 4
Ahora la cuenta es 5
Ahora la cuenta es 6
Ahora la cuenta es 7
*/

 

La recursividad no es otra cosa mas que una función que se llama a sí misma, es por lo tanto un bucle que debe tener una manera de terminar. En el programa, la variable index es colocada en 8 en la línea 8 y es utilizada como el argumento de la función llamada count_dn ( ). La función simplemente decrementa la variable, despliega un mensaje, y si la variable es mayor que cero, se llama a sí misma donde decrementa la variable una vez más, despliega un mensaje, etc, etc,etc. Finalmente la variable alcanza el valor de cero y la función ya no se llama a sí misma, en lugar de esto retorna al punto previo a su llamada, y retorna de nueva cuenta, y de nuevo, hasta que finalmente retorna a la función main ( ) y de aquí retorna al sistema operativo. Para que le resulte mas claro piense como si tuviera ocho funciones llamadas count_dn disponible y que llama una a la vez manteniendo un registro de en cual copia estuvo en determinado momento, esto no es en realidad lo que sucede en el programa pero a manera de comparación resulta útil para comprender el funcionamiento del programa.

Cuando Usted llama a la función desde la misma función, esta alamacena todas la variables y demas datos que necesita para completar la función en un bloque interno. La siguiente vez que es llamada la función hace exactamente lo mismo creando otro bloque interno, este ciclo se repite hasta alcanzar la última llamada a la función, entonces empieza a regresar los bloques utilizando estos para completar cada llamada de función. Los bloques son almacenados en una parte interna de la computadora llamada stack, esta es una parte de la memoria cuidadosamente organizada para almacenar datos de la manera ya descrita.

Al utilizar la recursividad es posible que Usted desee escribir un programa con recursividad indirecta, opuesta a la recursividad directa descrita arriba. La recursividad indirecta puede ser cuando una función A llama a una función B, la cual a su vez llama a la función A, etc. Esto es completamente permisible ya que el sistema tomará cuidado de almacenar en stack los datos para regresarlos cuando sea necesario. Recuerde que en la recursividad, en algún punto algo debe llegar a cero o alcanzar un punto predefinido para terminar el bucle. Si esto no es así, Usted tendrá un bucle infinito, en determinado momento el stack se saturará resultando en un mensaje de error y terminando el programa abruptamente.