Por ejemplo, el factorial puede definirse de manera recursiva de la siguiente manera:
Para definir una función en forma recursiva es necesario especificar:
- Caso(s) base: Donde la recursividad se detiene
- Paso de recursión: Como se define un elemento distinto del base, en términos de elementos anteriores.
int factorial(int n) {
if ((n == 0) || (n == 1))
return(1);
else
return(n*factorial(n-1));
}
Normalmente las definiciones recursivas pueden expresarse en forma no recursiva. Sin embargo, dependiendo del caso, el resultado puede ser más confuso. Por ejemplo, una función en C que calcula el factorial en forma iterativa sería:int factorial(int n) {
int i, fact = 1;
for (i=2; i<=n; i++)
fact = fact * i;
return(fact);
}
Sin embargo, los algoritmos iterativos tienen una ventaja en cuanto al uso de memoria, si se comparan con los iterativos. La recursividad requiere que se guarde el estado de la ejecución antes de cada llamado recursivo, implicando un gasto considerable de memoria. Es probable que, por esta razón, las versiones recursivas tengan mayores limitaciones al ejecutarse en un computador.La aplicación de las definiciones recursivas puede ampliarse a una amplia gama de problemas, en los que la solución más natural puede ser la que se expresa de esta forma. Por ejemplo, para buscar un número en un vector podemos tener una función que reciba como argumento el vector, el rango de búsqueda y el número buscado. El prototipo de esta función sería como:
int busqueda(int vec[], int inicio, int fin, int num);La función que quiere hacer la búsqueda haría el llamado indicando los rangos apropiados para el vector:
resultado = busqueda(vector, 0, N, x);La función busqueda( ) puede hacer su trabajo partiendo el vector en dos partes y llamándose a sí misma en forma recursiva, de la siguiente manera:
res1 = busqueda(vec, inicio, fin-inicio/2, num); res2 = busqueda(vec, (fin-inicio/2)+1, fin, num);El caso base sería cuando el vector que recibe la función busqueda( ) contiene un único elemento. En este caso simplemente compara el elemento con el número buscado y retorna el valor apropiado.
Más adelante, en el capítulo sobre Ordenamiento y Búsqueda, se tratará en detalle este algoritmo que recibe el nombre de
Ejemplo: Números de Fibonacci
La Sucesión de Fibonacci es una secuencia de números naturales, que empieza con 0 y 1, y cuyos siguientes términos están definidos como la suma de los dos anteriores:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Algoritmo Recursivo
Es bastante sencillo y natural definir la Sucesión de Fibonacci en forma recursiva:
A partir de esta definición, se puede escribir una función en C que genere el término n-ésimo de la sucesión. En el siguiente ejemplo se presenta esta función, junto con un programa de prueba que pide un número entero al usuario y determina el correspondiente término de la sucesión.
Existen muchas funciones matemáticas cuyos argumentos son números naturales, que pueden definirse de manera recursiva. Esto quiere decir que el valor de la función para el argumento n puede definirse en términos del argumento n-1 (o alguno anterior). En este tipo de definiciones siempre existirá un caso base a partir del cual parte la definición, el cual normalmente es el valor de la función en cero o en uno, aunque no necesariamente debe ser así.
Por ejemplo, el factorial puede definirse de manera recursiva de la siguiente manera:
Para definir una función en forma recursiva es necesario especificar:
- Caso(s) base: Donde la recursividad se detiene
- Paso de recursión: Como se define un elemento distinto del base, en términos de elementos anteriores.
int factorial(int n) {
if ((n == 0) || (n == 1))
return(1);
else
return(n*factorial(n-1));
}
Normalmente las definiciones recursivas pueden expresarse en forma no recursiva. Sin embargo, dependiendo del caso, el resultado puede ser más confuso. Por ejemplo, una función en C que calcula el factorial en forma iterativa sería:int factorial(int n) {
int i, fact = 1;
for (i=2; i<=n; i++)
fact = fact * i;
return(fact);
}
Sin embargo, los algoritmos iterativos tienen una ventaja en cuanto al uso de memoria, si se comparan con los iterativos. La recursividad requiere que se guarde el estado de la ejecución antes de cada llamado recursivo, implicando un gasto considerable de memoria. Es probable que, por esta razón, las versiones recursivas tengan mayores limitaciones al ejecutarse en un computador.La aplicación de las definiciones recursivas puede ampliarse a una amplia gama de problemas, en los que la solución más natural puede ser la que se expresa de esta forma. Por ejemplo, para buscar un número en un vector podemos tener una función que reciba como argumento el vector, el rango de búsqueda y el número buscado. El prototipo de esta función sería como:
int busqueda(int vec[], int inicio, int fin, int num);La función que quiere hacer la búsqueda haría el llamado indicando los rangos apropiados para el vector:
resultado = busqueda(vector, 0, N, x);La función busqueda( ) puede hacer su trabajo partiendo el vector en dos partes y llamándose a sí misma en forma recursiva, de la siguiente manera:
res1 = busqueda(vec, inicio, fin-inicio/2, num); res2 = busqueda(vec, (fin-inicio/2)+1, fin, num);El caso base sería cuando el vector que recibe la función busqueda( ) contiene un único elemento. En este caso simplemente compara el elemento con el número buscado y retorna el valor apropiado.
Más adelante, en el capítulo sobre Ordenamiento y Búsqueda, se tratará en detalle este algoritmo que recibe el nombre de
Ejemplo: Números de Fibonacci
La Sucesión de Fibonacci es una secuencia de números naturales, que empieza con 0 y 1, y cuyos siguientes términos están definidos como la suma de los dos anteriores:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Algoritmo Recursivo
Es bastante sencillo y natural definir la Sucesión de Fibonacci en forma recursiva: A partir de esta definición, se puede escribir una función en C que genere el término n-ésimo de la sucesión. En el siguiente ejemplo se presenta esta función, junto con un programa de prueba que pide un número entero al usuario y determina el correspondiente término de la sucesión.
Experimento Sugerido
Como se mencionó al introducir la recursividad, la implementación recursiva de un algoritmo normalmente consume más memoria que su contraparte recursiva. Esto se debe a que es necesario guardar el estado actual de la ejecución antes de cada llamado recursivo. Esto puede provocar limitaciones importantes en los programas que emplean funciones recursivas.Se sugiere probar los dos programas ofrecidos en esta sección para valores altos (a partir de 20) y comparar los resultados obtenidos.
Variantes Propuestas
A manera de ejercicio pueden escribirse variantes de este programa, que empleen la función Fibonacci, ya sea iterativa o recursiva:- Programa que lee un número y dice si pertenece a la Sucesión de Fibonacci.
- Programa lee un número entero n y despliega en pantalla los primeros n términos de la Sucesión de Fibonacci. En este caso, ¿existe alguna ventaja en usar una versión sobre la otra?, ¿por qué?.
Ejemplo: Obtención del máximo en un vector de enteros
En este ejemplo mostraremos una función recursiva para encontrar el valor máximo en un vector de números enteros. Se incluye un programa de prueba que recibe los valores del vector del usuario y despliega el valor máximo calculado mediante la función mencionada.Algoritmo
La definición recursiva de la función para obtener el máximo puede hacerse como:- Si el vector tiene un único elemento, ese elemento es el máximo (caso base).
- Si el valor en la posición inicial del vector es mayor que el maximo del resto del vector, entonces el valor de la primera posición es el máximo global.
- Si el valor en la posición inicial del vector es menor que el maximo del resto del vector, entonces el máximo global será el máximo en el resto del vector.
Ejemplo: Función para calcular módulo
El operador binario módulo obtiene el resto o residuo de la división de dos números enteros.Es bastante sencillo definir en forma recursiva la operación m mód n. La idea es ir restando el divisor del dividendo y calculando de nuevo el módulo, pues el resultado es el mismo. La recursividad se detiene cuando el divisor es mayor que el dividendo. En ese caso el resultado es el dividendo. La definición sería:
A partir de esta definición, se puede escribir una función en C que calcule m mód n, con m y n como los parámetros de la función. En el siguiente ejemplo se presenta esta función, junto con un programa de prueba que pide dos números enteros al usuario, calcula la operación y muestra en pantalla el resultado.
No hay comentarios:
Publicar un comentario