4.7.- Funciones recursivas

Se dice que una función es recursiva cuando puede invocarse a sí misma. En cada invocación se crean las variables locales, por lo que es indispensable incluir una condición de salida, ya que de no hacerlo se agotará la memoria disponible en la pila.

Como un primer acercamiento al manejo de funciones recursivas en C++, se presenta el listado 4.7.

  #include <iostream.h>                                     
  #include <conio.h>                                                
  #define NL cout << "\n" #define PULSE cout << "PULSE CUALQUIER TECLA PARA CONTINUAR." void recursiva(void); void main(void) { clrscr(); recursiva(); NL; PULSE; getch(); NL; } void recursiva(void) { int x; cout << "TECLEE UN NUMERO ENTERO... ( 0="SALIR)" "; cin>> x ;                                                 
    if(x)                                                      
    recursiva();                                             
  }

Listado 4.7.- Diseño de una función recursiva.


En el listado 4.7 podemos observar que, para que la función recursiva se invoque a si misma, es necesario que el valor almacenado en x sea diferente de 0.

El cálculo del factorial de un número es un problema clásico en la aplicación de las funciones recursivas. En el listado 4.8 se presenta un programa en C++ que calcula el factorial de un número dado. 

  #include <iostream.h>                                     
  #include <conio.h>                                               
                                                               
  long factorial(unsigned short int);                         
                                                               
  void main()                                                  
  {                                                            
    unsigned short int num;                                    
    long result;                                               
    clrscr();                                                  
    do {                                                       
             gotoxy(20,11);                                        
             cout << "El FACTORIAL del número: " ; clreol(); cin>> num ;                                          
          } while((num <0) || (num> 19 ));                      
    result = factorial(num);                                   
    gotoxy(20,13);                                             
    cout << " es : " << result; } long factorial(unsigned short int n) { if(n="=0)" return 1; else return n*(factorial(n-1)) ; }

Listado 4.8.- Cálculo del factorial utilizando funciones recursivas.

En el listado 4.8, si el número dado por el usuario es 4, el proceso realizado por el programa se podría representar de la manera mostrada en la tabla 4.2.

Numero de
invocación		Valor de nResultado
144*(factorial(3))
233*(factorial(2))
322*(factorial(1))
411*(factorial(0))
501

Tabla 4.2.- Resultados de invocar a la función factorial() pasándole como parámetro el número 4 .


En cada invocación, se crea en la pila una variable cuyo identificador es n y su valor cambiará como se muestra en la tabla 4.2. Como en las invocaciones 1,2,3 y 4 el valor de n es diferente de 0, la función vuelve a invocarse a sí misma, quedando sin resolver el resultado.
Cuando el valor de n es igual a 0 (invocación 5), la función retorna el valor 1 la la invocación 4, por lo que el resultado en ésta se calcula así :

             1 * (factorial(0)) = 1 * 1 = 1

La invocación 4 retorna a la invocación 3 el valor 1 y el resultado en la invocación 4 es :

             2 * (factorial(1)) = 2 * 1 = 2

A su vez, la invocación 3 retorna a la invocación 2 el valor 2. El resultado en la invocación 2 es :

             3 * (factorial(2)) = 3 * 2 = 6

Posteriormente, la invocación 2 retorna el valor 6 a la invocación 1. El resultado en la invocación 1 es :

             4 * (factorial(3)) = 4 * 6 = 24

Finalmente, la invocación 1 retorna el valor 24 a la función invocadora main(), la cual asigna a la variable result el valor recibido ( 24 ).


Página anterior Página siguiente