PDF de programación - Un poco sobre programación Recursiva

Un Poco Sobre Programación Recursiva.



Un Poco Sobre Programación Recursiva

Tradicionalmente estamos acostumbrados a programar computadoras bajo el
viejo (pero no por eso malo) esquema de “arriba a abajo” (top-down, dirían los de habla
inglesa). Han surgido variantes que ayudan a mejorar el entendimiento y mantenimiento
de programas so sólo aquellos hechos por otros, sino por uno mismo, como la
programación estructurada y otros esquemas que rompen la linealidad en cuanto al
seguimiento del flujo de programa, y hace que ese flujo dependa de eventos, como clics
de ratón, pulsar una tecla, cumplimiento de un temporizador, etc., que se conoce como
Programación Orientada a Objetos.



En cualquiera de esos esquemas de programación puede insertarse en forma incidental
la llamada Programación Recursiva, que consiste en sunciones que pueden invocarse a
si mismas hasta alcanzar un criterio de parada. El ejemplo clásico de este tipo de
programas lo constituye sin dudas, el cálculo del factorial de un número entero mayor o
igual a cero (es decir, perteneciente al conjunto Z, que incluye a los positivos más el
cero), ya que:


(*

n

−

)!1



=

!
n
n
1!0

=


Teniendo por criterio de parada la convención de que 0! = 1.

En programación tradicional, resolvemos fácilmente el problema de la siguiente
manera:


#Leer n
F = n
Repita para i = 1,n-1
F = F*(n-i)
Fin RP.
Imprimir F



Figura 1. Versión procedimental para el cálculo de factorial

Pero, utilizando el hecho de que El factorial de n depende del factorial de sus
predecesores (recursividad), en el orden natural de los números enteros, podemos
utilizar (si el lenguaje de programación que estamos utilizando lo permite, como ocurre
con C/C++) un esquema más elegante como el que aparece a continuación:



#include <iostream>
using namespace std;

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

Cosme Rafael Marcano Gamero.

1

Un Poco Sobre Programación Recursiva.



int n;
cout << "Introduzca valor de n: " ;
cin >> n;
cout << fr(n) << endl;
}



Figura 3. Versión recursiva para el cálculo de factorial


Nótese que lo primero que chequea el código reentrante de la función fr() es el criterio
de parada, es decir, si el argumento es igual a cero, en cuyo caso retorna 1, de acuerdo a
lo establecido en la definición del factorial. De lo contrario, procede a invocarse a sí
misma con el valor del argumento decrementando en uno. El proceso se repite hasta que
el argumento se haga igual a cero, en cuyo caso fr() retornará 1 y el programa podrá
realizar en forma inversa los cálculos necesarios para resolver el factorial del número
originalmente pasado como argumento.


Muchos métodos de cálculo de raíces de funciones algebraicas, así como de
búsqueda de datos dentro de bases de datos muy extensas se pueden resolver utilizando
la recursividad.

Así, por ejemplo, el método numérico de cálculo aproximado de una raíz de una función
real de una sola variable real, como es el conocido Método de Bisección, es susceptible
de ser codificado en forma recursiva.


A continuación se muestran dos implementaciones de ese método de cálculo de

raíces: uno en forma tradicional y el otro en forma recursiva.



#include <stdio.h>
#include <math.h>
#include <math.h>

float x2,y2;
float f(float x){
return (x*x-2);
}
float biseccion(float a, float b, float error)
{
float x1, x2, y0, y1;
x2 = (a+b)/2;
y2 = f(x2);
y0 = f(a);
y1 = f(b);
while (fabs(y2) > error)
{
if (y0*y2<0){
b = x2;
y1 = y2;
} else
{
a = x2;
y0 = y2;
}
x2 = (a+b)/2;
y2 = f(x2);

Cosme Rafael Marcano Gamero.

2

Un Poco Sobre Programación Recursiva.



}
return (x2);
}

int main()
{
float x0,x1,y0,y1,X0o,X1o,Xi;
printf("Introduzca valor de x0: ");
scanf("%f",&x0);
y0 = f(x0);
printf("Introduzca valor de x1: ");
scanf("%f",&x1);
y1 = f(x1);

X0o = x0; // para preservar el valor original default:x0
X1o = x1; // para preservar el valor original default:x1

printf("Introduzca valor de Xi (error permitido): ");
scanf("%f",&Xi);

if (y0*y1 > 0){
printf("\naparentemente no hay ra\241ces en el intervalo [%f, %f]", x0, x1 );
} else
{
x2 = biseccion(x0,x1,Xi);
printf("\n\nValor aproximado de
%7.3f",X0o,X1o,x2,Xi);
}

}


la ra\241z dentro de

[%7.3f, %7.3f] = %7.3f, +/-

Figura 3. Versión procedimental para el Método de Bisección.

(bisec.cpp)



#include <stdio.h>
#include <math.h>

float x2,y2;
float f(float x){
return (x*x-2);
}
float biseccion(float a, float b, float error)
{
float x1, x2, y0, y1;
x2 = (a+b)/2;
y2 = f(x2);
// x0 = a;
y0 = f(a);
y1 = f(b);

if (y0*y2<0){
b = x2;
y1 = y2;
} else{
a = x2;
y0 = y2;
}
if (fabs(y2) < error) return (x2); // se alcanzó la precisión deseada
else return(biseccion(a, b, error));

Cosme Rafael Marcano Gamero.

3

Un Poco Sobre Programación Recursiva.



}

int main()
{
float x0,x1,y0,y1,X0o,X1o,Xi;
printf("Introduzca valor de x0: ");
scanf("%f",&x0);
y0 = f(x0);
printf("Introduzca valor de x1: ");
scanf("%f",&x1);
y1 = f(x1);

X0o = x0; // para preservar el valor original default:x0
X1o = x1; // para preservar el valor original default:x1

printf("Introduzca valor de Xi (error permitido): ");
scanf("%f",&Xi);

if (y0*y1 > 0){
printf("\nAparentemente no hay ra\241ces en el intervalo [%f, %f]", x0, x1 );
} else
{
x2 = biseccion(x0,x1,Xi);
printf("\n\nValor aproximado de
%8.5f",X0o,X1o,x2,Xi);
}
}

la ra\241z dentro de

[%6.3f, %6.3f] = %8.5f, +/-

Figura 4. Versión recursiva para el Método de Bisección.

(biserec.cpp)


Obviamente, hay una serie de condiciones que debe cumplir la función sometida
. La función devbe ser continua en todo el
a este método, en este caso
intervalo
, el cual debe contener una y sólo una raíz. En caso de raíces múltiples
de la función dentro de ese intervalo, el método dirá, o bien que no hay ninguna, en caso
de raíces pares (ya que
), o bien dará resultados impredecibles, dependiendo
de los extremos del intervalo, en caso de raíces múltiples impares.

0 xx
1

)(
xf

* 1

>y

= x

y

0

2 −

2

0

[

,

]

]


En este caso, la función es una parábola que abre hacia arriba y corta al eje
. Además cumple

y tiene dos raíces en

2−=y

4142

±=

.1

2
vertical en
perfectamente con las condiciones exigidas por el método.

±=x
2,1


Otros métodos numéricos son susceptibles de ser implementados en forma
recursiva. Por ejemplo, como ejercicio se puede codificar el método de la secante. La
Figura 5 muestra la gráfica de f(x).



Figura5 Gráfica de f(x)



Cosme Rafael Marcano Gamero.

4

Un Poco Sobre Programación Recursiva.



A continuación se muestran los resultados que arrojan las dos versiones del

método, los cuales coinciden perfectamente.



Figura 6. Resultados arrojados por bisec.exe y biserec.exe


Por analogía inmediata, el método de bisección (casi continuo) se asemeja al de
Búsqueda Binaria (caso discreto), que se utiliza para buscar un elemento de un arreglos
de datos. Los datos dentro del arreglo deben estar ordenados (ascendente o
descendentemente). La idea es dividir recursivamente el arreglo en dos partes, e ir
desechando el segmento que contiene las claves mayores a la que se busca, y proseguir
la búsqueda seccionado en dos partes, no necesariamente iguales en tamaño.


La recursividad es particularmente útil en el manejo de Estructuras de Datos
Dinámicas, desde pilas, hasta Árboles Binarios de Búsqueda (ABB). Esto se debe a la
propia definición recursiva de estas estructuras de datos, lo cual será tratado en otro
material de estudio.



Notas:

1. Los segmentos de código que se muestran aquí están compilados utilizando
el compilador g++ de Twilight Dragon Media (TDM), versión 4.4,1 el cual
está disponible gratuitamente en Internet. Este compilador es compatible
con aquellos pertenecientes a la familia de compiladores conocidos
genéricamente como gcc, o Gnu C Compilers, del proyecto GNU, también
de distribución gratuita a través de Internet. Sin embargo, pueden ser
transportados a casi cualquier otra implementación de C++, como Borland
C/C++ Builderversión 6.0 o Microsoft Visual Studio 10 Express.

2. La gráfica contenida en la Figura 5 se obtuvo utilizando la librería OpenCV
(Open source Computer Vision), de Intel Corporation, la cual es una
poderosa herramienta de distribución gratuita, que se puede utilizar para
aplicaciones que manejan gráficos, imágenes y videos, por lo que es
especialmente útil en proyectos de Visión por Computadora. Estas librerías
serán introducidas en orto material, actualmente en preparación.

Cosme Rafael Marcano Gamero.

5