FACULTAD DE INGENIERIA
DIRECCION DE ING. EN SISTEMAS
CATEDRA: ESTRUCTURA DE DATOS
PROFESOR: GERMAN A. SALAS OJEDA
GUIA DE ESTUDIO
RESUMEN_001
Desde que fui estudiante siempre he sabido lo difícil que es entender qué es la recursividad y para qué sirve
en computación. Para muchos la única forma de aprender a dominar esta importante técnica de programación
es correr mentalmente muchos programas recursivos, hasta que, por insistencia, se llega a entender de qué
trata este asunto. Como profesor, he tratado de explicar este importante concepto. Como la recursividad es
un concepto fundamental en computación, quiero compartir mi experiencia en la enseñanza de esta técnica
de programación. Agradeceré cualquier sugerencia que ayude a mejorar este trabajo.
¿QUE ES LA RECURSIVIDAD? La recursividad es una técnica de programación interesante y a veces útil, en
donde se llama a la función desde el cuerpo de la propia función. Por supuesto, si eso es todo lo que hace, se
estaría llamando a la función hasta que se acabase la memoria de ejecución, de modo que debe existir una
manera de «escaparse» de la llamada recursiva.
Aunque es un concepto que puede llegar a ser muy complejo, en esencia es muy sencillo: La recursividad
consiste en funciones que se llaman a sí mismas, evitando el uso de bucles y otros iteradores. Un ejemplo
fácil de ver y que se usa a menudo es el cálculo del factorial de un número entero. El factorial de un número
se define como ese número multiplicado por el anterior, éste por el anterior, y así sucesivamente hasta llegar
a 1. Así, por ejemplo, el factorial del número 5 sería: 5x4x3x2x1 = 120. Tomando el factorial como base para
un ejemplo, ¿cómo podemos crear una función que calcule el factorial de un número? Bueno, existen multitud
de formas. La más obvia quizá sería simplemente usar un bucle determinado para hacerlo, algo así en
JavaScript:
function factorial(n){
var res = 1;
for(var i=n; i>=1; i--){
res = res * i;
}
return res;
}
Sin embargo, hay otra forma de hacerlo sin necesidad de usar ninguna estructura de bucle que es mediante
recursividad. Esta versión de la función hace exactamente lo mismo, pero es más corta, más simple y más
elegante:
function factorial(n) {
if (n<=1) return 1;
return n* factorial(n-1);
}
Aquí lo que se hace es que la función se llama a sí misma (eso es recursividad), y deja de llamarse cuando se
cumple la condición de parada: en este caso que el argumento sea menor o igual que 1 (que es lo que hay en
el condicional). Es decir, cuando llamamos a la primera función, ésta se llama a sí misma, pero pasándole un
número menos y así sucesivamente hasta llegar a la última (la que recibe un 1 y por lo tanto deja de hacer
más llamadas). En el momento en el que alguna de ellas empieza a devolver valores "hacia atrás", regresa la
llamada a cada una de ellas, los valores devueltos se van multiplicando por el parámetro original en cada una
de ellas, hasta llegar arriba del todo en el que la primera llamada devuelve el valor buscado. Es un concepto
que cuesta un poco entender pero que es muy poderoso.
El concepto de recursividad pone una gran potencia al alcance del programador y adquiere una
dimensión fundamental en los llamados lenguajes de programación funcionales, los cuales a
menudo no incorporan sentencias que permitan crear bucles, debiendo recurrir a las llamadas
recursivas para implementar repeticiones.
Se pueden establecer diferentes categorías de recursividad en virtud de la característica del
algoritmo analizada:
Según el punto desde el cual se hace la llamada recursiva: recursividad directa o indirecta.
Según el número de llamadas recursivas efectuadas en tiempo de ejecución: recursividad
lineal o no lineal.
Según el punto del algoritmo desde donde se efectúa la llamada recursiva: recursividad
final o no final.
Para obtener más información respecto a los lenguajes de programación funcionales, consulta la
dirección Web http://es.wikipedia.org/wiki/Programaci%C3%B3n_funcional
La mayoría de los algoritmos que pueden ser descritos de forma iterativa (es decir, haciendo uso de
bucles while, for…) pueden ser reescritos de forma recursiva, y viceversa. Al hablar de funciones
recursivas, nos referimos a algoritmos recursivos implementados en un lenguaje particular. Aunque
hemos elegido el término genérico función, pueden emplearse otros similares como procedimiento
o método.
¿Cuándo utilizar la recursión?
Para empezar, algunos lenguajes de programación no admiten el uso de recursividad, como por ejemplo el
ensamblador o el FORTRAN. Es obvio que en ese caso se requerirá una solución no recursiva (iterativa).
Tampoco se debe utilizar cuando la solución iterativa sea clara a simple vista. Sin embargo, en otros casos,
obtener una solución iterativa es mucho más complicado que una solución recursiva, y es entonces cuando se
puede plantear la duda de si merece la pena transformar la solución recursiva en otra iterativa.
Posteriormente se explicará cómo eliminar la recursión, y se basa en almacenar en una pila los valores de las
variables locales que haya para un procedimiento en cada llamada recursiva. Esto reduce la claridad del
programa. Aun así, hay que considerar que el compilador transformará la solución recursiva en una iterativa,
utilizando una pila, para cuando compile al código del computador. Por otra parte, casi todos los algoritmos
basados en los esquemas de vuelta atrás y divide y vencerás son recursivos, pues de alguna manera parece
mucho más natural una solución recursiva.
Aunque parezca mentira, es en general mucho más sencillo escribir un programa recursivo que su equivalente
iterativo. Se propondrán diversos ejemplos de programas recursivos de diversa complejidad para
acostumbrarse a la recursión.
Ventajas e inconvenientes
¿Ganamos algo al utilizar recursión en lugar de bucles/iteradores para casos como este? En este caso concreto
del cálculo factorial no, y de hecho es una forma más lenta de hacerlo y ocupa más memoria. Esto no es
preocupante en la realidad, pero conviene saberlo. Lo del factorial es solo una forma de explicarlo con un
ejemplo sencillo y que sea fácil de entender. Pero entonces, si no ganamos nada en este caso ¿para qué sirve
realmente la recursividad? Pues para resolver ciertos problemas de manera elegante y eficiente.
Para poder compilar este código en C++ puedes ingresar a https://www.onlinegdb.com/online_c++_compiler
que es un compilador de varios lenguajes de programación.
Programa en C++ que calcula el producto de dos números de forma recursiva. Los números a multiplicar se
leen por teclado.
#include <iostream>
using namespace std;
int producto(int, int); //Declaración y llamada a la función
int main() //Menú
{
int n1,n2,p; //Declaración de variables
cout << "Introduzca primer número: ";
cin >> n1;
cout << "Introduzca segundo numero: ";
cin >> n2;
p=producto(n1,n2);
cout << "producto: " << p << endl;
}
int producto(int a, int b) //Función recursiva
{
if(a==0 or b==0) //if decisor
return 0;
else
{
return a+producto(a,b-1); //llamada a si misma
}
}
Programa C++ que calcula la factorial de un número de forma recursiva.
#include <iostream>
using namespace std;
long double factorial(int);
int main()
{ int n;
cout << "Introduzca número: ";
cin >> n;
cout << "factorial: " << factorial(n) << endl;
system("pause");
}
long double factorial(int n)
{
long double fact;
if (n==0)
return 1;
else
return n*factorial(n-1);
}
Ejercicios
1.- Generar el MCD de dos números de manera recursiva ingresados por teclado, positivos, si son negativos
indicar que no son válidos. La salida debe ser generada parecido a lo siguiente:
2.- Generar un programa recursivo que invierta el número ingresado por teclado
3.- Genere un programa recursivo que me indique si la palabra es un Palíndromo o no. Nota: Un Palíndromo
es una palabra que se lee igual de derecha a inquiera.
