PDF de programación - Tema 5 - Recursividad en Pascal

En Pascal, a un procedimiento o función le es permitido no sólo invocar a otro procedimiento o función, sino
En Pascal, a un procedimiento o función le es permitido no sólo invocar a otro procedimiento o función, sino
En Pascal, a un procedimiento o función le es permitido no sólo invocar a otro procedimiento o función, sino
también invocarse a sí mismo. Una invocación de éste tipo se dice que es recursiva.
también invocarse a sí mismo. Una invocación de éste tipo se dice que es recursiva.
también invocarse a sí mismo. Una invocación de éste tipo se dice que es recursiva.

5. Recursividad en Pascal
5. Recursividad en Pascal
5. Recursividad en Pascal

La función recursiva más utilizada como ejemplo es la que calcula el factorial de un número entero no
La función recursiva más utilizada como ejemplo es la que calcula el factorial de un número entero no
La función recursiva más utilizada como ejemplo es la que calcula el factorial de un número entero no
negativo, partiendo de las siguientes definiciones :
negativo, partiendo de las siguientes definiciones :
negativo, partiendo de las siguientes definiciones :

factorial (0) = 1
factorial (0) = 1
factorial (0) = 1
factorial (n) = n*factorial(n-1), para n>0
factorial (n) = n*factorial(n-1), para n>0
factorial (n) = n*factorial(n-1), para n>0

La función, escrita en Pascal, queda de la siguiente manera :
La función, escrita en Pascal, queda de la siguiente manera :
La función, escrita en Pascal, queda de la siguiente manera :

function factorial(numero:integer):integer;
function factorial(numero:integer):integer;
function factorial(numero:integer):integer;
begin
begin
begin
if numero = 0 then
if numero = 0 then
if numero = 0 then
factorial := 1
factorial := 1
factorial := 1
else
else
else
factorial := numero * factorial(numero-1)
factorial := numero * factorial(numero-1)
factorial := numero * factorial(numero-1)

end;
end;
end;

Si numero = 4, la función realiza los siguientes pasos :
Si numero = 4, la función realiza los siguientes pasos :
Si numero = 4, la función realiza los siguientes pasos :

1.
1.
1.

2.
2.
2.

3.
3.
3.

4.
4.
4.

factorial(4) := 4 * factorial(3) Se invoca a si misma y crea una segunda variable cuyo nombre es
factorial(4) := 4 * factorial(3) Se invoca a si misma y crea una segunda variable cuyo nombre es
factorial(4) := 4 * factorial(3) Se invoca a si misma y crea una segunda variable cuyo nombre es
numero y su valor es igual a 3.
numero y su valor es igual a 3.
numero y su valor es igual a 3.
factorial(3) := 3 * factorial(2) Se invoca a si misma y crea una tercera variable cuyo nombre es
factorial(3) := 3 * factorial(2) Se invoca a si misma y crea una tercera variable cuyo nombre es
factorial(3) := 3 * factorial(2) Se invoca a si misma y crea una tercera variable cuyo nombre es
numero y su valor es igual a 2.
numero y su valor es igual a 2.
numero y su valor es igual a 2.
factorial(2) := 2 * factorial(1) Se invoca a si misma y crea una cuarta variable cuyo nombre es
factorial(2) := 2 * factorial(1) Se invoca a si misma y crea una cuarta variable cuyo nombre es
factorial(2) := 2 * factorial(1) Se invoca a si misma y crea una cuarta variable cuyo nombre es
numero y su valor es igual a 1.
numero y su valor es igual a 1.
numero y su valor es igual a 1.
factorial(1) := 1 * factorial(0) Se invoca a si misma y crea una quinta variable cuyo nombre es
factorial(1) := 1 * factorial(0) Se invoca a si misma y crea una quinta variable cuyo nombre es
factorial(1) := 1 * factorial(0) Se invoca a si misma y crea una quinta variable cuyo nombre es
numero y su valor es igual a 0.
numero y su valor es igual a 0.
numero y su valor es igual a 0.

5. Como factorial(0) := 1, con éste valor se regresa a completar la invocación: factorial(1) := 1 * 1 , por
5. Como factorial(0) := 1, con éste valor se regresa a completar la invocación: factorial(1) := 1 * 1 , por
5. Como factorial(0) := 1, con éste valor se regresa a completar la invocación: factorial(1) := 1 * 1 , por

lo que factorial(1) := 1
lo que factorial(1) := 1
lo que factorial(1) := 1

6. Con factorial(1) := 1, se regresa a completar: factorial(2) := 2 * 1, por lo que factorial(2) := 2
6. Con factorial(1) := 1, se regresa a completar: factorial(2) := 2 * 1, por lo que factorial(2) := 2
6. Con factorial(1) := 1, se regresa a completar: factorial(2) := 2 * 1, por lo que factorial(2) := 2
7. Con factorial(2) := 2, se regresa a completar : factorial(3) := 3 * 2, por lo que factorial(3) := 6
7. Con factorial(2) := 2, se regresa a completar : factorial(3) := 3 * 2, por lo que factorial(3) := 6
7. Con factorial(2) := 2, se regresa a completar : factorial(3) := 3 * 2, por lo que factorial(3) := 6
8. Con factorial(3) := 6, se regresa a completar : factorial(4) := 4 * 6, por lo que factorial(4) := 24 y éste
8. Con factorial(3) := 6, se regresa a completar : factorial(4) := 4 * 6, por lo que factorial(4) := 24 y éste
8. Con factorial(3) := 6, se regresa a completar : factorial(4) := 4 * 6, por lo que factorial(4) := 24 y éste
será el valor que la función factorial devolverá al módulo que la haya invocado con un valor de
será el valor que la función factorial devolverá al módulo que la haya invocado con un valor de
será el valor que la función factorial devolverá al módulo que la haya invocado con un valor de
parámetro local igual a 4 .
parámetro local igual a 4 .
parámetro local igual a 4 .

Un ejemplo de procedimiento recursivo es el
siguiente:
Supóngase que una persona se mete a una piscina cuya profundidad es de 5 metros. Su intención es
tocar el fondo de la piscina y después salir a la superficie. Tanto en el descenso como en el
ascenso se le va indicando la distancia desde la superficie (a cada metro).

Program Piscina; Uses Crt;

Const
prof_max = 5;
Var
profundidad:int
eger;
procedure zambullida(Var profun :integer);
begin
WriteLn('BAJA 1 PROFUNDIDAD = ',profun);
profun := profun + 1;
if profun <=
prof_max then
zambullida(profun)
else
WriteLn;
profun := profun - 1;
WriteLn('SUBE 1 PROFUNDIDAD = ', profun-1)
end; begin ClrScr;
profundidad := 1;
zambullida(profundidad)
end.

5. Recursividad Lenguaje C

La recursividad es la posibilidad de que una función se llame a sí misma, bien directa o
indirectamente. Un ejemplo típico es el cálculo del factorial de un número, definido en la forma:

N! = N * (N-1)! = N * (N-1) (N-2)! = N * (N-1)*(N-2)*...*2*1

La función factorial, escrita de forma recursiva, sería como sigue:

unsigned long factorial(unsigned long numero)
{

if ( numero == 1 || numero == 0 )

return 1;

else

return numero*factorial(numero-1);

}

Supóngase la llamada a esta función para N=4, es decir factorial(4). Cuando se llame por
primera vez a la función, la variable numero valdrá 4, y por tanto devolverá el valor de
4*factorial(3); pero factorial(3) devolverá 3*factorial(2); factorial(2) a su vez es 2*factorial(1)
y dado que factorial(1) es igual a 1 (es importante considerar que sin éste u otro caso particular,
llamado caso base, la función recursiva no terminaría nunca de llamarse a sí misma), el resultado final
será 4*(3*(2*1)).

Por lo general la recursividad no ahorra memoria, pues ha de mantenerse una pila7 con los
valores que están siendo procesados. Tampoco es más rápida, sino más bien todo lo contrario, pero
el código recursivo es más compacto y a menudo más sencillo de escribir y comprender.

Gestión dinámica de la memoria

Según lo visto hasta ahora, la reserva o asignación de memoria para vectores y matrices se hace
de forma automática con la declaración de dichas variables, asignando suficiente memoria para
resolver el problema de tamaño máximo, dejando el resto sin usar para problemas más pequeños.
Así, si en una función encargada de realizar un producto de matrices, éstas se dimensionan para un
tamaño máximo (100, 100), con dicha función se podrá calcular cualquier producto de un tamaño
igual o inferior, pero aun en el caso de que el producto sea por ejemplo de tamaño (3, 3), la
memoria reservada corresponderá al tamaño máximo (100, 100). Es muy útil el poder reservar más
o menos memoria en tiempo de ejecución, según el tamaño del caso concreto que se vaya a
resolver. A esto se llama reserva o gestión dinámica de memoria.

Existen en C dos funciones que reservan la cantidad de memoria deseada en tiempo de
ejecución. Dichas funciones devuelven –es decir, tienen como valor de retorno– un puntero a la
primera posición de la zona de memoria reservada. Estas funciones se llaman malloc() y calloc(), y
sus declaraciones, que están en la librería stdlib.h, son como sigue:

void *malloc(int n_bytes)

void *calloc(int n_datos, int tamaño_dato)

La función malloc() busca en la memoria el espacio requerido, lo reserva y devuelve un
puntero al primer elemento de la zona reservada. La función calloc() necesita dos argumentos: el nº

7 Una pila es un tipo especial de estructura de datos que se estudiará en INFORM ÁTICA 2.

de celdas de memoria deseadas y el tamaño en bytes de cada celda; se devuelve un puntero a la
primera celda de memoria. La función calloc() tiene una propiedad adicional: inicializa todos
los bloques a cero.

Existe también una función llamada free() que deja libre la memoria reservada por malloc() o
calloc() y que ya no se va a utilizar. Esta función usa como argumento el puntero devuelto por
calloc() o malloc(). La memoria no se libera por defecto, sino que el programador tiene que
liberarla explícitamente con la función free(). El prototipo de esta función es el siguiente:

void free(void *)

A continuación se presenta un ejemplo de gestión dinámica de memoria para el producto de
matriz por vector {y}=[a]{x}. Hay que tener en cuenta que reservando memoria por separado
para cada fila de la matriz, no se garantiza que las filas estén contiguas en la memoria. Por
otra parte, de esta forma se pueden considerar filas de distinto tamaño. El nombre de la matriz se
declara como puntero a vector de punteros, y los nombres de los vectores como punteros
(recuérdese la figura 6.