Programación en C

FUNCIONES - LLAMADAS RECURSIVAS

¿Qué sucede si una función contiene una llamada a esa misma función? Evidentemente, nos encontraremos ante una sucesión de activaciones de la función. En cada activación se reserva algo de memoria en la pila, tanto más cuanto mayor sea el número de parámetros formales y de variables locales en general. Si el proceso continúa, la pila acaba por invadir zonas de memoria que no le han sido asignadas, y el programa acaba por sufrir un error fatal. Ahora bien, podemos asegurarnos de que esa colección de activaciones sucesivas se detenga cuando se haya calculado un cierto valor. Considérese el ejemplo siguiente:

#include<stdio.h>

#define MAX 16

long calculo(long numero);

int main(int argc, char * argv[])
{
 long n;

 do {
  printf("Deme un número entero entre 1 y %d: ", MAX);
  scanf("%d", &n);
  fpurge(stdin);
 } while ( n < 1 || n > MAX);

 printf("El factorial de %d es %d\n", n, calculo(n));

 return 0;

}


long calculo(long numero)
 {
  if (numero == 1)
   return numero;
  else
   return numero*calculo(numero-1);
 }
/*
Deme un número entero entre 1 y 16: 4
El factorial de 4 es 24
*/

Comentarios .- Obsérvese la sencillez (elegancia, en la jerga informática) de la función


			calculo()

. ¡Esta función contiene una llamada a sí misma!. La idea es sencilla: el factorial de 1 es 1, por definición. Si el número es 1, devolvemos 1 como factorial. Si el número es mayor que 1, digamos

, está claro que


			n! = n*(n-1)!

, esto es, que el factorial de

es igual a

multiplicado por el factorial de

n-1

. Eso se expresa sin dificultad alguna mediante la sentencia


			if-else

que constituye el bloque de la función


			calculo()

. La sucesión de llamadas recursivas se detiene, finalmente, cuando el valor del parámetro real que se le proporciona es 1. Es instructivo seguir los valores que va tomando


			número

, y sobre todo los valores que proporciona la sentencia


			return

, a medida que progresa la sucesión de llamadas recursivas. Considérese esta nueva versión del programa, que proporciona idénticos resultados pero muestra la ruta de ejecución del código:

#include<stdio.h>

#define MAX 16

int numero_de_llamadas = 0;
long calculo(long numero);

int main(int argc, char * argv[])
{
 long n;
 long resultado;

 do {
  printf("Deme un número entero entre 1 y %d: ", MAX);
  scanf("%d", &n);
  fpurge(stdin);
 } while ( n < 1 || n > MAX);

 resultado = calculo(n);
 printf("El factorial de %d es %d\n", n, resultado);

 return 0;

}


long calculo(long numero)
 {
  long valor_proporcionado;
  int num_esta_llamada = numero_de_llamadas++;
  printf("Entrada - llamada: %d - número recibido: %d\n",
    num_esta_llamada, numero);
  if (numero == 1)
   valor_proporcionado = numero;
  else
   valor_proporcionado = numero*calculo(numero-1);
  printf("Salida - número de llamada %d- devuelve: %d\n",
    num_esta_llamada,
    valor_proporcionado);
  return valor_proporcionado;
 }

/*
Deme un número entero entre 1 y 16: 10
Entrada - llamada: 0 - número recibido: 10
Entrada - llamada: 1 - número recibido: 9
Entrada - llamada: 2 - número recibido: 8
Entrada - llamada: 3 - número recibido: 7
Entrada - llamada: 4 - número recibido: 6
Entrada - llamada: 5 - número recibido: 5
Entrada - llamada: 6 - número recibido: 4
Entrada - llamada: 7 - número recibido: 3
Entrada - llamada: 8 - número recibido: 2
Entrada - llamada: 9 - número recibido: 1
Salida - número de llamada 9- devuelve: 1
Salida - número de llamada 8- devuelve: 2
Salida - número de llamada 7- devuelve: 6
Salida - número de llamada 6- devuelve: 24
Salida - número de llamada 5- devuelve: 120
Salida - número de llamada 4- devuelve: 720
Salida - número de llamada 3- devuelve: 5040
Salida - número de llamada 2- devuelve: 40320
Salida - número de llamada 1- devuelve: 362880
Salida - número de llamada 0- devuelve: 3628800
El factorial de 10 es 3628800
*/

Comentarios .- Este resultado es realmente interesante, porque muestra la sucesión inicial de entradas en la función; en cada una de ellas se va reduciendo en 1 el valor del número recibido, hasta llegar a 1 en la llamada 9. Entonces comienzan los retornos; el primero es de la llamada número 9 y proporciona, claro el valor 1. Luego retorna de la llamada 8, y devuelve 2 (el número que recibió en la llamada 8, según se ve más arriba) multiplicado por 1. A continuación retorna de la llamada 7, que recibió el valor 3 y por tanto multiplica 3 por lo recibido de 8, que es 2. El resultado obtenido al retornar de la llamada 7 es, por tanto, 3 x 2 = 6. El resto sigue idéntica pauta.

Las funciones recursivas son, en muchas ocasiones, una forma elegante de resolver problemas complejos. Desafortunadamente, el gran consumo de memoria en que incurren puede hacerlas poco aconsejables. El lector interesado hallará aquí muchos algoritmos relacionados con funciones recursivas.

Volver a la parte superior de esta página