Recursión en Pascal

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.

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:

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

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

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

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  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
  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
  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 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:integer;
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.