Programación funcional con recursividad
Sistema
de tipos
Un sistema de tipos define como
un lenguaje de programación clasifica los valores y las expresiones en tipos,
cómo se pueden manipular estos tipos y cómo interactúan. Un tipo indica un
conjunto de valores que tienen el mismo significado genérico o propósito
(aunque algunos tipos, como los tipos de datos abstractos y tipos de datos
función, tal vez no representen valores en el programa que se está ejecutando).
Los sistemas de tipificación varían significativamente entre lenguajes, siendo
quizás las más importantes variaciones las que estén en sus implementaciones de
la sintáctica en tiempo de compilación y la operativa en tiempo de ejecución.
Se entiende bajo el término
sistema a un conjunto de elementos que están relacionadas entre sí para
alcanzar algún determinado objetivo.
Pueden clasificarse tomando en cuenta diversos criterios, algunos de
ellos son los siguientes:
- Según la relación que establecen con el
medio ambiente:
Sistemas cerrados: se caracterizan por su hermetismo, que hace que no
ocasionen ningún intercambio con el ambiente que se encuentra a su alrededor,
por lo que no se ven afectados por el mismo.
Esto hace que tampoco los sistemas ejerzan influencia alguna en el medio
ambiente que los rodea. Los sistemas cerrados entonces, se caracterizan por
poseer un comportamiento totalmente programado y determinado y la materia y
energía que intercambian con el ambiente que los rodea es mínima.
Sistemas abiertos: estos sí establecen
intercambios con el medio ambiente que los rodea. Para lograr esto se
valen de salidas y entradas por medio de las que intercambian, de manera
constante, energía y materia con el medio ambiente. Este vínculo que se
establece hace que los sistemas abiertos deban ser sumamente adaptativos a las
cualidades del ambiente del cual dependen, sino es así, no logran la
supervivencia. Esta dependencia con lo ajeno hace que no puedan existir de
forma aislada y que deban adaptarse por medio de la organización y del
aprendizaje a los cambios externos.
- Según su constitución:
Sistemas conceptuales: están constituidos por conceptos que son ajenos
a la realidad y que resultan meramente abstractos.
Sistemas físicos: los elementos que los componen, en cambio, son
concretos y palpables, es decir que se los puede captar por medio del tacto.
- Según su origen:
Sistemas artificiales: se caracterizan por ser producto de la creación
humana, por lo que dependen de la presencia de otros para poder existir.
Sistemas naturales: estos en cambio, no dependen de la mano de obra
del hombre para originarse.
- Según su movimiento:
Sistemas dinámicos: estos sistemas se caracterizan por presentar
movimiento.
Sistemas estáticos: como su nombre indica, carecen de movimiento
alguno.
- Según la complejidad de los elementos que
los conforman:
Sistemas complejos: se caracterizan por estar compuestos por una serie
de subsistemas, lo que vuelve difícil la tarea de identificar los distintos
elementos que los componen.
Sistemas simples: a diferencia de los anteriores, éstos no cuentan con
subsistemas, lo que permite identificar fácilmente a los elementos
constitutivos de los mismos.
- Según su naturaleza:
Sistemas inertes: carece de vida alguna.
Sistemas vivos: estos, en cambio, si poseen vida.
PROGRAMACION II. RECURSIVIDAD
Recursividad:
La recursividad es una técnica de programación que se utiliza para
realizar una llamada a una
función desde ella misma, de allí su nombre. El ejemplo más utilizado
por su fácil comprensión es
el cálculo de números factoriales. El factorial de 0 es, por
definición, 1. Los factoriales de números
mayores se calculan mediante la multiplicación de 1 * 2 * ...,
incrementando el número de 1 en 1
hasta llegar al número para el que se está calculando el factorial.
Un algoritmo recursivo es un algoritmo que expresa la solución de un
problema en términos de
una llamada a sí mismo. La llamada a sí mismo se conoce como llamada
recursiva o recurrente.
#include <iostream>
#include <cstdlib>
using namespace std;
int Factorial(int n);
int main(){
int valor;
system("clear");
cout << "Introduzca
numero a calcular: ";
cin >> valor;
cout << "\nEl
Factorial de " << valor << " es: " <<
Factorial(valor) << endl;
return 0;
}
int Factorial(int n){
if (n < 0){
cout << “No existe el
factorial de un numero negativo.\n”;
}else if(n < 2){
return 1;
}else
return n * Factorial(n-1);
}
Generalmente, si la primera
llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada
nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza
que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo
progresivamente la complejidad del problema a resolver, llegará un momento en
que su resolución sea más o menos trivial (o, al menos, suficientemente
manejable como para resolverlo de forma no recursiva). En esa situación diremos
que estamos ante un caso base de la recursividad.
Es frecuente que los algoritmos
recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser
mucho más breves en espacio.
Recursividad directa vs indirecta.
Cuando en una subrutina hay llamadas a ella
misma se habla de recursividad directa en contraposición, cuando se tienen
varias subrutinas y éstas se llaman unas a otras formando ciclos se dice que la
recursión es
indirecta
.Subrutina_A → Subrutina_A →
Subrutina_A
Subrutina_A → Subrutina_B → Subrutina_C
→ Subrutina_D → Subrutina_A
Propiedades
de las definiciones o algoritmos recursivos:
No debe generar una secuencia
infinita de llamadas así mismo, dicho de otro modo ha de existir al menos un
caso base.
PROGRAMACION
II. RECURSIVIDAD
Una función recursiva debe
definirse en términos que no impliquen a al menos en un argumento o grupo de
argumentos.
Debe existir una
"salida" de la secuencia de llamadas recursivas.
Cada llamada recurrente se debería definir sobre un problema de menor
complejidad (algo
más fácil de resolver).
Programación Recursiva:
Es mucho mas difícil desarrollar una solución recursiva en un lenguaje
determinado para resolver
un problema especifico cuando no se tiene un algoritmo. No es solo el
programa sino las
definiciones originales y los algoritmos los que deben desarrollarse.
En general, cuando encaramos
la tarea de escribir un programa para resolver un problema no hay
razón para buscar una solución
recursiva. La mayoría de los problemas pueden resolverse de una manera
directa usando métodos
no recursivos. Sin embargo, otros pueden resolverse de una manera mas
lógica y elegante mediante la recursión. Volviendo a examinar la función
factorial. El factor es, probablemente, un ejemplo fundamental de un problema
que no debe resolverse de manera recursiva, dado que su solución iterativa es
directa y simple. Sin embargo, examinaremos los elementos que permiten dar una
solución recursiva. Antes que nada, puede reconocerse un gran número de casos
distintos que se deben resolver. Es decir, quiere escribirse un programa para
calcular 0!, 1!, 2! Y así sucesivamente. Puede identificarse un caso
"trivial" para el cual la solución no recursiva pueda obtenerse en
forma directa. Es el caso de 0!, que se define como 1. El siguiente paso es
encontrar un método para resolver un caso "complejo" en términos de
uno mas "simple", lo cual permite la reducción de un problema
complejo a uno mas simple. La transformación del caso complejo al simple
resultaría al final en el caso trivial. Esto significaría que el caso complejo
se define, en lo fundamental, en términos del mas simple. En el modelo de
evaluacion de los lenguajes funcionales, el usuario introduce una expresion que
es evaluada por el sistema. La evaluacion consiste en bus-car subexpresiones
dentro de la expresi ́on que puedan transformarse utilizando
las funciones predefinidas y las funciones definidas por el usuario.
Cuando no es posible realizar m ́as transformaciones se dice que se ha
alcanzado la forma normal
.Existen dos estrategias fundamentales de evaluaci ́on:
evaluacion aplicativa y evaluacion normal
.En la evaluaci ́on aplicativa, se eligen las subexpresiones m ́as
internas de la
expresi ́on, mientras que en la evaluaci ́on normal, se eligen las
subexpresiones m ́as externas. Sup ́ongase que se definen las funciones
La estrategia de evaluaci ́on aplicativa tambi ́en se conoce como
llamada por valor
(call by value). Ya que se eval ́uan primero los argumentos de la
funci ́on y
se le pasan a la funci ́on sus valores.La estrategia de evaluaci ́on
normal se conoce como
llamada por nombre(call by name), indicando que se pasan las expresiones,
en lugar de sus valores. Dichas expresiones no son evaluadas si no se necesita
su valor.
En ocasiones, la llamada por nombre puede hacer que ciertas
subexpresionesse evaluen mas de una vez
El sistema de tipos de Haskell posee una
característica que lo distingue de otros lenguajes de
programación. El tipo de polimorfismo del que hemos
tratado hasta ahora es denominado polimorfismo paramétrico.
Existe otro tipo de polimorfismo llamado ad hoc o sobrecarga. Estos son algunos
ejemplos de polimorfismo ad hoces una descripción
informal1 de alto nivel de un algoritmo informático
de programación, compacto e informal, que utiliza las
convenciones estructurales de un lenguaje de programación
verdadero2 , pero que está diseñado para la lectura humana en lugar de la
lectura mediante máquina, y con independencia de cualquier otro
lenguaje de programación.
aplicaciones en rutinas de pseudocodigo:
No hay comentarios:
Publicar un comentario