PDF de programación - Ejemplo de recursividad, cálculo del factorial

Ejemplo de recursividad, calculo del factorial.

Cuando se explico como se denen funciones en C++, no se establecio ninguna restric-
cion a las instrucciones que pueden escribirse en el cuerpo de una funcion. Por lo tanto es
posible escribir en el cuerpo de una funcion llamadas a la misma funcion. Una llamada a
una funcion desde la misma funcion se denomina llamada recursiva y se puede decir que
la funcion es recursiva o bien que utiliza la recursividad.
La recursividad es la forma mas sencilla de escribir en un lenguaje de programacion la de-
nicion de acciones inductivas. Un ejemplo de una accion inductiva es el calculo del factorial
de un numero natural:

x! = ( 1 si x=0

x(x-1)! si x>0

En C++ se podra escribir esa accion de la siguiente forma:

int factorial(int x)
{
if (x==0) return 1;
else return x*factorial(x-1);
}

En la gura 1 se muestra un diagrama con las sucesivas llamadas recursivas a la funcion
factorial y el retorno de las mismas. Los pasos que sigue el programa se numeran desde 0 a
7. A continuacion se explica cada uno de ellos:

Paso 0: el valor del parametro real se copia en el parametro formal x. Como su valor
no es cero, se ejecuta la sentencia incluida en el else. Dicha sentencia incluye una
llamada recursiva a factorial con el valor 2.

Paso 1: el valor 2 se copia en x, del mismo modo que en el caso anterior, se ejecuta la
sentencia incluida en el else, produciendose otra llamada recursiva a factorial, en
este caso con el valor 1.

Paso 2: el valor 1 se copia en x, como ocurra en el caso anterior, se ejecuta la sentencia
incluida en el else, produciendose otra llamada recursiva a factorial, en este caso
con el valor 0.

Paso 3: el valor 0 se copia en x. En este caso se cumple la condicion del if, de modo
que se retorna 1 y no se efectua ninguna llamada recursiva.

Paso 4: el valor de retorno 1 sustituye a la llamada factorial(1-1), de modo que se
puede calcular la expresion 1*factorial(1-1), su valor es 1.

1

#include<iostream>
using namespace std;
int factorial(int x)
{
if (x==0) return 1;
else return x*factorial(x−1);
}
main()
{
int a=factorial(3);
}

1

0

x=3;

x=2;

2

x=1;

3

x=0;

return 3*factorial(3−1);

return 2*factorial(2−1);

return1*factorial(1−1);

return 1;

7

6

5

4

Figura 1: Diagrama de las llamadas recursivas a la funcion factorial.

Paso 5: el valor de retorno 1 sustituye a la llamada factorial(2-1), de modo que se
puede calcular la expresion 2*factorial(2-1), su valor es 2.

Paso 6: el valor de retorno 2 sustituye a la llamada factorial(3-1), de modo que se
puede calcular la expresion 3*factorial(3-1), su valor es 6.

Paso 7: el valor de retorno 6 sustituye a la llamada factorial(3) y se asigna a la
variable a, el programa termina.

La funcion anterior podra haberse escrito sin utilizar la recursividad, en forma iterativa,

del siguiente modo:

int factorial(int x)
{
int f=1;
for (int i=2;i<x;i++)

f=f*x;

return f;
}

Las dos funciones realizan el mismo calculo utilizando las mismas operaciones, pero la forma
recursiva emplea mayor cantidad de memoria (el paso del parametro es por valor) y ademas
existe el coste añadido de las sucesivas llamadas, las cuales conllevan un determinado tiempo
de procesador. En general una funcion no es recursiva o iterativa intrnsecamente: para cada
funcion recursiva existe una funcion iterativa con su misma especicacion, y viceversa. Es
frecuente codicar de forma recursiva una funcion cuando su version iterativa es muy com-
pleja.

2