algoritmo recursivo

Algoritmo Recursivo

Un algoritmo recursivo es un algoritmo que se define en términos de sí mismo. Son implementados en forma de subrutinas (funciones, procedimientos, subprogramas, etc) de tal forma que dentro de un subrutina recursiva hay una o más llamadas a sí misma.
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecuciónrecurrente 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 anteun caso base de la recursividad.
Las claves para construir un subprograma recurrente son:
Cada llamada recurrente se debería definir sobre un problema de menor complejidad
Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.
Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.Partes
1.- Condición a evaluar según la aproximación al límite establecido.
2.- Llamada al método recursivo si la condición no se cumple.
Uno de los ejemplos más clásicos es el factorial de un número. Intenta seguir la explicación razonando cada paso. Para cualquier entero positivo N, el factorial de N (que se expresa como N!) es el producto (multiplicación) de todos los enteros menor a él:1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 6
4! = 1 x 2 x 3 x 4 = 24
5! = 1 x 2 x 3 x 4 x 5 = 120
6! = 1 x 2 x 3 x 4 x 5 x 6 = 720
Ahora, repasando atentamente, se puede ver que el factorial de cada número incluye el factorial de todos los números anteriores a él. Lo escrito en corchetes rectos a continuación es una referencia, no a nivel matemático:
“2!” es “1[1!] x 2″
“3!” es “(1 x 2)[2!] x3″
Y así sucesivamente. Para cualquier entero N mayor a 1, podemos decir que el factorial de N es igual al factorial del número anterior a N multiplicado por N. La fórmula N! = (N-1)! x N. Vuelve a la lista de factoriales de 1 a 6. Busca en cada caso los términos que son factorial del número anterior para darte cuenta. Entonces se podria decir que una buena practica es encontrar el factor en elresultado que se repite.
Pasando ésto a función en C, podemos hacer una función a la que le pasamos un número, y nos devuelve el factorial:
int factorial(int n){
return n * factorial(n - 1);
}
Ahí tenemos nuestra primera función recursiva. Pero si compilamos el código y ejecutamos el programita, obtenemos una hermosa violación de segmento.
El problema es que la función definida arriba notermina nunca, va a seguir restándole 1 a N por siempre. Siempre vamos a poder restarle 1 a cualquier n, por lo que la función va a seguir ejecutándose a sí misma por siempre. Además, para cualquier número positivo, factorial de n va a devolver 0, porque cualquier multiplicación con 0 como término devuelve 0. Y restarle 1 recursivamente a cualquier entero positivo, eventualmente dará cero.
Para quela función recursiva esté completa, además de llamarse a sí misma, necesita una forma de finalizar, una condición.
Por definición, el factorial de 1 es 1 (1!=1) así como el factorial de 0 (0!=1)también es 1. Por lo que podemos implementar ésta condición para que la función no sea interminable.
Así, la definición de la función consta de la recursiva que se llama a sí misma, y la condición paradetenerse.
Asimismo, puede definirse un programa en términos recursivos, como una serie de pasos básicos, o paso base (también conocido como condición de parada), y un paso recursivo, donde vuelve a llamarse al programa. En un computador, esta serie de pasos recursivos debe ser finita, terminando con un paso base. Es decir, a cada paso recursivo se reduce el número de pasos que hay que dar para...