Estructura de datos

Unidad II

Recursividad

Rubi veronica chimal Cuxin.

Ingeniería en sistemas computacionales

INSTITUTO TECNOLÓGICO SUPERIOR DE FELIPE CARRILLO PUERTO

Introducción

Comprender y aplicar la recursividad como herramienta de programación para el manejo de las estructuras de datos es indispensable pues en la carrera de un Ing. En sistemas computacionales podemos consultar en fuentes impresas el concepto de recursividad así se puede ejemplificar un caso recursivo de la vida cotidiana como calcular el Factorial de un número entero positivo. Para poder entenderle por completo hay que realizar varios ejercicios para poder identificar problemas resueltos de manera iterativa y encontrar su solución recursiva mediante codificación en algún lenguaje de programación así como analizar las ventajas y desventajas que este pudiese tener.

Código

El factorial de un entero n, se expresa como un conjunto de productos:

n * (n-1) * (n-2) * …… * 1

Escribiendo el código en lenguaje C usando el ciclo for es de la siguiente manera:

int i, factorial; factorial=1;

for(i=numero;i>=1;i--) factorial*= i;

Por ejemplo 5!, claramente es lo mismo que 5*4!, como se muestra mediante el siguiente:

5!=55!=5*(4*3*2*1)5!=5*(4!)

En la figura mostrada a continuación muestra la sucesión de llamadas recursivas continúa hasta que 1! Se evalúa al valor 1, lo que termina la recursión. En la figura del lado derecho se muestran los valores regresados por cada llamada recursiva a su llamador, hasta que el valor final es calculado y regresado.

La función recursiva factorial primero prueba para ver si una condición de terminación es verdadera, es decir, es número menor que o igual a

1. Si número es en verdad menor que o igual a 1 factorial regresa 1, ya no es necesaria mayor recursión y el programa termina.

El código sería el siguiente:

using System;namespace ConsoleApplication14{ /// <summary> /// Esta clase /// <SUMMARY> class factorial { int numero; int fact(int num) { numero=num; if(numero<=1) return 1; else return(numero*fact(numero-1)); } [STAThread] static void Main(string[] args) { factorial f1=new factorial(); Console.WriteLine("Dame el número para calcular su factorial"); int p,n; n=int.Parse(Console.ReadLine()); p=f1.fact(n); Console.WriteLine("El factorial es:\n"); Console.Write(p+"\n"); } }}

Conclusión

En los programas se han analizado e implementado funciones que llaman unas a otras. Para algunos tipos de problemas, es útil tener funciones que se llamen a sí mismas. Una función recursiva es una función que se llama a sí misma, ya sea directa o indirectamente a través de otra función, esta es llamada para resolver un problema. La función sabe sólo cómo resolver el caso más simple, es decir, el llamado caso base. Si la función es llamada con un problema más complejo, la función divide dicho problema en dos partes conceptuales: una parte que la función ya sabe cómo ejecutar y una parte que la función no sabe cómo ejecutar. Para hacer factible la recursión, esta última parte debe parecerse al problema original, la función llama a una copia nueva de sí misma, para que empiece a trabajar sobre el problema más pequeño y esto se conoce como una llamada recursiva y también se llama el paso de recursión. El paso de recursión también incluye la palabra reservada return, porque el resultado será combinado con la parte del problema que la función supo cómo resolver para formar un resultado que será regresado al llamador original, posiblemente main.