Recursividad Un algoritmo recursivo es un algoritmo que expresa la solucin de un problema en trminos de una llamada a s mismo.
La llamada a s mismo se conoce como llamada recursiva o recurrente. FUNCIN Factorial(n) VAR resultado: Entero SI (n<2) ENTONCES resultado = 1; SINO resultado = n * Factorial(n-1); FSI RETORNA resultado; FFUNCIN Recursividad: La recursividad es una tcnica de programacin importante. Se utiliza para realizar una llamada a una funcin desde la misma funcin. Como ejemplo til se puede presentar el clculo de nmeros factoriales. l factorial de 0 es, por definicin, 1. Los factoriales de nmeros mayores se calculan mediante la multiplicacin de 1 * 2 * ..., incrementando el nmero de 1 en 1 hasta llegar al nmero para el que se est calculando el factorial. El siguiente prrafomuestra una funcin, expresada con palabras, que calcula un factorial. "Si el nmero es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el nmero es cero, su factorial es uno. Si el nmero es mayor que cero, se multiplica por l factorial del nmero menor inmediato." Para calcular el factorial de cualquier nmero mayor que cero hay que calcular como mnimo el factorial de otro nmero. La funcin que se utiliza es la funcin en la que se encuentra en estos momentos, esta funcin debe llamarse a s misma para el nmero menor inmediato, para poder ejecutarse en el nmero actual. Esto es un ejemplo de recursividad. La recursividad y la iteracin (ejecucin en bucle) estn muy relacionadas, cualquier accin que pueda realizarse con la recursividad puede realizarse con iteracin y
viceversa. Normalmente, un clculo determinado se prestar a una tcnica u otra, slo necesita elegir el enfoque ms natural o con el que se sienta ms cmodo. Claramente, esta tcnica puede constituir un modo de meterse en problemas. Es fcil crear una funcin recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalizacin. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito". Para entender mejor lo que en realidad es el concepto de recursin veamos un poco lo referente a la secuencia de Fibonacci. Principalmente habra que aclarar que es un ejemplo menos familiar que el del factorial, que consiste en la secuencia de enteros. 0,1,1,2,3,5,8,13,21,34,..., Cada elemento en esta secuencia es la suma de los precedentes (por ejemplo 0 + 1 = 0, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, ...) sean fib(0) = 0, fib (1) = 1 y as sucesivamente, entonces puede definirse la secuencia de Fibonacci mediante la definicin recursiva (define un objeto en trminos de un caso mas simple de si mismo): fib (n) = n if n = = 0 or n = = 1 fib (n) = fib (n - 2) + fib (n - 1) if n >= 2 Por ejemplo, para calcular fib (6), puede aplicarse la definicin de manera recursiva para obtener: Fib (6) = fib (4) + fib (5) = fib (2) + fib (3) + fib (5) = fib (0) + fib (1) + fib (3) + fib (5) = 0 + 1 fib (3) + fib (5) 1. + fib (1) + fib (2) + fib(5) = 1. + 1 + fib(0) + fib (1) + fib (5) = 2. + 0 + 1 + fib(5) = 3 + fib (3) + fib (4) = 3 + 1 + fib (0) + fib (1) + fib (4) = 3. + fib (1) + fib (2) + fib (4) = 4. + 0 + 1 + fib (2) + fib (3) = 5 + fib (0) + fib (1) + fib (3) = 5. + 0 + 1 + fib (1) + fib (2) = 6 + 1 + fib (0) + fib (1) = 6. + 0 + 1 = 8 7.
Recursividad versus iteracin La recursividad y la iteracin (ejecucin en bucle) estn muy relacionadas, cualquier accin que pueda realizarse con la recursividad puede realizarse con iteracin y viceversa. Normalmente, un clculo determinado se prestar a una tcnica u otra, slo necesita elegir el enfoque ms natural o con el que se sienta ms cmodo. Tanto la iteracin como la recursin se basan en una estructura de control: -la iteracin utiliza una estructura repetitiva -la recursin utiliza una estructura de seleccin. La iteracin y la recursin implican ambas repeticin: -la iteracin utiliza explcitamente una estructura repetitiva -la recursin consume la repeticin mediante llamadas repetidas. La iteracin y la recursin implican cada una un test mientras que la recursin termina cuando se reconoce un caso base o la condicin de salida se alcanza. Recursividad versus iteracin
Ventajas y desventajas Ventajas de la Recursin
Soluciones simples, claras Soluciones elegantes. Soluciones a problemas complejos. Desventajas de la Recursin: INEFICIENCIA Sobrecarga asociada con las llamadas a subalgoritmos Una simple llamada puede generar un gran numero de llamadas recursivas. (Fact(n) genera n llamadas recursivas) La claridad compensa la sobrecarga? El valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fcil solucin iterativa. -La ineficiencia inherente de algunos algoritmos recursivos. La recursividad se debe usar cuando sea realmente necesaria, es decir, cuando no exista una solucin iterativa simple. Ejercicios 1 2 3 4 5 6 La secuencia de Fibonacci La potencia La multiplicacin de 2 nmeros La sumatoria de los n primeros nmeros naturales La sumatoria desde a hasta b
