Estructura De Datos

Programación No Numérica I
0

Fact(N) =
(N es entero positivo)

Si se quiere entonces codificar una rutina para el cálculo del
factorial, podemos usar la forma iterativa tradicional o la forma
recursiva.
Revisemos la función factorial “Fact” de forma iterativa y luego
de forma recursiva.
FUNCIÓN ITERATIVA
int Fact(int N)
{
int F=1;

// Se inicializa una variable local F, queservirá de acumulador en el proceso iterativo

for (int J=N;J>=1;J--)

// Se crea un ciclo que se ejecutará N veces

F = F * J;
return F;

// El acumulador almacenara las
multiplicaciones sucesivas por J desde 1
hasta N (ó desde N hasta 1)

};

Pág. 12

Programación No Numérica I

FUNCIÓN RECURSIVA
int Fact(int N)
{
if (N==0)
return 1;
else
return (N * Fact(N-1));
};

//Se verifica el caso base:
//Si el valor del parámetro N es igual a 0 ,
por definición del factorial la respuesta es 1,
entonces, retorna directamente 1.
// Si N > 0, se descompone el factorial,
como lo indica la función matemática, o sea
que sería N * Fact(N-1)

Pág. 13

Programación No Numérica I

Recursividad vs. Iteración
- Tanto la iteración como la recursión implican repetición.La
iteración utiliza estructuras repetitivas directamente, mientras que la
recursión lo hace por llamados repetidos a la misma rutina.
- Tanto la iteración como la recursión necesitan una condición de
salida. La iteración termina cuando la condición del bucle no se
cumple, mientras que la recursión termina cuando se reconoce el
caso base.
- La iteración se ejecuta más rápidamente y utilizamenos
memoria que la recursión. Sin embargo, la recursión es deseable
cuando la iteración no es clara ni evidente

Pág. 14

Programación No Numérica I

SEGUIMIENTO DE UNA RUTINA RECURSIVA
Para hacer un seguimiento a las rutinas recursivas vamos a
visualizar el comportamiento en la memoria al momento de la
ejecución, esto es, trataremos de visualizar:
•
•
•
•

Los valores de lasvariables globales
La dirección de retorno de la rutina
Los valores de las variables locales
Los parámetros actuales

En la llamada a la misma rutina N veces en el proceso
recursivo, es necesario el uso de la “Pila Interna” del computador,
para guardar todos estos elementos: dirección de retorno,
variables locales y parámetros actuales de la rutina. A cada uno de
estos elementos losidentificaremos de esta forma:
•

Los valores de las variables globales en rojo.
Ej: Valor=5

•

La dirección de retorno de la rutina en azul, colocando DR,
luego la identificación de la llamada, empezando por cero 0 la
primera llamada, luego 1, 2,…, seguido por un número que
identifica la línea de código donde se dispara la llamada:
Ej: DR->0-2, DR->1-5

•

Los parámetros actuales de larutina en verde
Ej: N=2

•

Los valores de las variables locales en naranja
Ej: X=0
Ejemplo Factorial:
int Fact(int N)
{
if (N==0)
return 1;
else
return (N * Fact(N-1));
};

Pág. 15

Programación No Numérica I

Si la llamada de la función factorial se hace para N=3, la línea
de código donde se hace la llamada podría ser por ejemplo:
1. N=3;
2. cout 1-3
N=3
DR->0-2PILA INTERNA

N=0
DR->3-3
N=1
DR->2-3
N=2
DR->1-3
N=3
DR->0-2

Programación No Numérica I

En la etapa regresiva se sacan de la pila los parámetros de la
rutina y la dirección de retorno y se va hacia esa dirección para
continuar la ejecución del programa
ETAPA REGRESIVA:
MEMORIA
1. N=3;
2. cout 0-2

PILA INTERNA

N=1
DR->2-3
N=2
DR->1-3
N=3
DR->0-2

Programación NoNumérica I

Ejemplo Factorial con variables locales:
int Fact(int N)
{
int x,y;
if (N==0)
return 1;
else
{
x=N-1;
y=Fact(x);
return (N * y);
};
};
Si la llamada de la función factorial se hace para N=3, la llamada
sería igualmente:
1. N=3;
2. cout 1-6
x=2,y=Fact(2)
N=3
DR->0-2

PILA INTERNA

x=?,y=?
N=0
DR->3-6
x=0,y=Fact(0)
N=1
DR->2-6
x=1,y=Fact(1)
N=2
DR->1-6...