Programacion

Recursividad
La recursividad es una técnica de programación importante, se utiliza para realizar una llamada a una función desde la misma función. En otras palabras, pueden llamarse a sí mismas directa o indirectamente. La recursividad directa es el proceso mediante el que una función se llama a sí misma desde el propio cuerpo de la función, mientras que la recursividad indirecta implica más deuna función. Un proceso recursivo tiene que tener una condición de finalización, ya que de lo contrario podría continuar infinitamente.
No todas las funciones pueden llamarse a sí mismas, sino que deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a que el programa termine inadecuadamente.
Tampoco todos los lenguajes de programaciónpermiten usar recursividad.
C++ permite la recursividad. Cada vez que se llama a una función, se crea un juego de variables locales, de este modo, si la función hace una llamada a sí misma, se guardan sus variables y parámetros, usando la pila, y la nueva instancia de la función trabajará con su propia copia de las variables locales. Cuando esta segunda instancia de la función retorna, recuperalas variables y los parámetros de la pila y continúa la ejecución en el punto en que había sido llamada.
Eficiencia de los algoritmos recursivos

Los algoritmos recursivos suelen ser menos eficientes en tiempo
Motivos:
1. Cada llamada requiere tiempo para
_ Hacer la llamada a la función
_ Crear las variables locales y copiar los parámetros por valor
_ Ejecutar las instrucciones en parteejecutiva de la función
_ Destruir las variables locales y parámetros por valor
_ Salir de la función
Calculo del factorial de un número
Explicación del código de c++
El caso base es que cuando n valga 1 o 0 retorna un 1, de lo contrario retorna la multiplicación de n * el factorial del número anterior n-1. Supongamos que introducimos el número 3, cuyo factorial es 6 (3*2*1 = 6).
1. n=3 Noentra al caso base. Guardamos para después la operación 3 * factorial(2)
2. n=2 No entra al caso base. Guardamos para después la operación 2 * factorial(1)
3. n=1 Entra al caso base. Retorna 1, por lo tanto factorial(1) = 1
4. Hacemos la última operación que guardamos 2 * factorial(1) = 2 * 1 = 2, por lo tanto factorial(2) = 2
5. Hacemos la siguiente operación que guardamos 3 *factorial(2) = 3 * 2 = 6
6. El factorial es 6

Vuelta atrás
Dentro de las técnicas de diseño de algoritmos, el método de Vuelta Atrás (del inglés Backtracking) es uno de los de más amplia utilización, en el sentido de que puede aplicarse en la resolución de un gran número de problemas, muy especialmente en aquellos de optimización.
Este se basa en recorrer el espacio completo de lassoluciones posibles al problema planteado. Esta técnica es la aplicación directa del método de búsqueda conocido como primero en profundidad. Típicamente, los algoritmos de vuelta atrás no realizan ningún tipo de optimización y recorren el árbol de soluciones completo. Sin embargo, es posible aplicarles una poda para no descender en aquellas ramas que, de antemano, se sabe que no conducen a una solución.Una mejora de los algoritmos de vuelta atrás son los algoritmos de Ramificación y poda.
Eficiencia
Si bien este tipo de algoritmos son por lo general ineficientes, en ocasiones es el único camino posible. Además, pueden considerarse otros métodos algorítmicos, como los algoritmos voraces o la programación dinámica, como optimizaciones de este método. El algoritmo básico de vuelta atrás es elsiguiente:
1. Tomar una opción de entre las posibles
2. Para cada elección, considerar toda opción posible recursivamente
3. Devolver la mejor solución encontrada
Esta metodología es lo suficientemente genérica como para ser aplicada en la mayoría de problemas. Por contra, incluso teniendo cuidado en la implementación, es muy probable que un algoritmo de vuelta atrás sea de tiempo...