Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Recursividad III




Enviado por Pablo Turmero



  1. Introducción
  2. Definición
  3. Algoritmo recursivo
  4. Conclusión
  5. Web
    grafía

Introducción

La recursividad es un concepto fundamental
en matemáticas y en computación. También la
podemos conocer como una alternativa diferente para implementar
estructuras de repetición en otras palabras ciclos. En los
módulos se hacen llamadas recursivas que se puede usar en
toda situación en la cual la solución pueda ser
expresada como una secuencia de movimientos, pasos o
transformaciones gobernadas por un conjunto de reglas no
ambiguas.

Para darle una idea concreta de lo que le
estaremos presentando en este trabajo le daremos un
pequeño ejemplo:

La Matrushka es una artesanía
tradicional rusa. Es una muñeca de madera que contiene
otra muñeca más pequeña dentro de sí.
Esta muñeca, también contiene otra muñeca
dentro. Y así, una dentro de otra.

Monografias.com

OBJETIVOS DEL TRABAJO

  • ¿Por qué escribir
    programas recursivos?

  • ¿Cómo escribir una
    función en forma recursiva?

  • ¿Cuándo usar la
    recursividad? o ¿Cuándo no usar la
    recursividad?

  • ¿Cómo diferenciar la
    recursividad de la iteración?

Definición

La recursividad es la forma en la cual se
especifica un proceso basado en su propia definición.
Siendo un poco más precisos, y para evitar el
aparente círculo sin fin.

La recursividad se considerar una
técnica de programación importante. Se utiliza para
realizar una llamada a una función desde la
misma función. Como ejemplo útil se puede presentar
el cálculo de números factoriales.
Él 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. La recursividad y la
iteración (ejecución en bucle) están muy
relacionadas, cualquier acción que pueda
realizarse con la recursividad puede realizarse con
iteración y viceversa. Normalmente, un cálculo
determinado se prestará a una técnica u otra,
sólo necesita elegir el enfoque más natural o con
el que se sienta más cómodo.

  • Ámbito de Aplicación:

Problemas cuya solución se puede hallar
solucionando el mismo problema pero con un caso de menor
tamaño.

  • Razones de uso:

– Problemas "casi" irresolubles con las estructuras
iterativas.

Soluciones elegantes.

– Soluciones más simples

Las claves para construir un programa recursivo
son:

  • Cada llamada recurrente se debería definir
    sobre un problema de menor complejidad (algo más
    fácil de resolver).

  • Ha de existir al menos un caso base para evitar que
    la recurrencia sea infinita.

Ejemplo en forma grafica de la
recursividad

Consideremos el cálculo del
factorial para n = 4, enviado como parámetro valor desde
otro subprograma o desde el programa principal:

n = 4    Llamada a
Factorial(4)  es n = 0;  No

           
Factorial = 4 * Factorial(3)

n = 3    Llamada a
Factorial(3)  es n = 0;  No

           
Factorial = 4 * 3 * Factorial(2)

n = 2    Llamada a
Factorial(2)  es n = 0;  No

           
Factorial = 4 * 3 * 2 * Factorial(1)

n = 1    Llamada a
Factorial(1)  es n = 0;  No

           
Factorial = 4 * 3 * 2 * 1 * Factorial(0)

n = 0    Llamada a
Factorial(0)  es n = 0;  Si

           
Factorial = 4 * 3 * 2 * 1 * 1

           
Factorial = 24

No es recomendable declarar a la
función factorial como int, ya que cuando
n = 8, 8! = 40320, este valor supera ampliamente el rango de los
enteros (32767).

Es mejor definirla de tipo long
int
o de tipo float.

La evaluación del factorial de 4
procede como se muestra en la gráfica
siguiente.

Seguimiento del algoritmo recursivo Factorial
(4!).

Monografias.com

En el extremo izquierdo se muestra el
proceso de sucesión de llamadas recursivas (proceso de
ida) hasta que se evalúa que 0! es igual a 1, con lo que
termina la recursión.

En el extremo derecho, se muestran los
valores que cada llamada recursiva que los devuelve al invocador,
hasta que se calcula y se devuelve el valor final.

Algoritmo
recursivo

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.

FUNCIÓN Factorial(n)

VAR resultado: Entero

SI (n<2) ENTONCES

resultado = 1;

SINO

resultado = n * Factorial(n-1);

FSI

RETORNA resultado;

FFUNCIÓN

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 que
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.

Programa Ejemplo

Monografias.com

Conclusión

Se puede decir que la recursividad es una
técnica de programación bastante útil y muy
interesante de estudiar. A través de los ejemplos que
el individuo pueda revisar, aprenderá con más
rapidez y sencillez lo que es programar recursivamente e incluir
esta técnica cuando se le presente un problema. La
asignación de memoria, sea estática o
dinámica, en realidad se tendrá que aplicar en
cualquier programa al momento de su codificación; tomando
en cuenta que cada programador tiene su estilo de programar. El
ejemplo de las muñecas Matrushka es un problema clave que
tienen que ver directamente con lo que es la
recursividad.

Web
grafía

  • Google Chrome. Recursividad.

http://www.lcc.uma.es/~lopez/modular/recursion/transp_recursion.pdf

  • Google Chrome. Eloy Pascal, Juan Navas.
    Recursividad. 11 de septiembre de 2003. 3 de junio de
    2011.

http://www.monografias.com/trabajos14/recursividad/recursividad#PROPIE

  • Mozilla Firefox. Carlos Romero Shollande.
    Recursividad. Viernes 8 de abril de 2011. Domingo 5 de Junio
    de 2011.
    http://caromeroshlp.blogspot.com/2011/04/recursividad.html

  • Internet Explorer. Tuc Negre. Algoritmo
    Recursivo. Miércoles, 23 de marzo de 2011. Domingo, 5
    de junio de 2011.
    http://es.wikipedia.org/wiki/Algoritmo_recursivo

 

Enviado por:

Pablo Turmero

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter