¿Cuál es la diferencia entre programación dinámica y recursividad?

Durante la recursión, puede existir un caso en el que los mismos subproblemas se resuelven varias veces.
Considere el ejemplo de calcular el enésimo número de fibonacci.
fibo (n) = fibo (n-1) + fibo (n-2)
ffibo (n-1) = fibo (n-2) + fibo (n-3)
fibo (n-2) = fibo (n-3) + ffibo (n-4)
……………………………
………………………… ..
………………………… ..
fibo (2) = fibo (1) + fibo (0)

En los primeros tres pasos, se puede ver claramente que el fibo (n-3) se calcula dos veces. Si uno profundiza en la recursividad, él / ella puede encontrar la repetición de los mismos subproblemas una y otra vez.

Beneficio de DP sobre recursión:
DP es una técnica que utiliza una tabla para almacenar los resultados del subproblema, de modo que si se vuelve a encontrar el mismo subproblema en el futuro, podría devolver directamente el resultado en lugar de volver a calcularlo.
Siga el siguiente enlace para más detalles:
Programación Dinámica | Conjunto 1 (Propiedad de subproblemas superpuestos) – GeeksforGeeks

La recursión es solo una función que se llama a sí misma. No está relacionado con la programación dinámica, como Recursion vs Iteration. También puede usar la recursividad en su programación dinámica. Al llegar a la programación dinámica, la mayoría de los problemas de DP pueden resolverse mediante una recursión de arriba hacia abajo o un enfoque de almacenamiento en caché de resultados intermedios, una técnica que se llama ‘memorización’.

Puede almacenar en caché los resultados mientras usa la recursividad también.

Una diferencia importante al usar estos dos métodos para resolver un problema es que en el enfoque ‘recursivo’ de arriba hacia abajo no necesita calcular todos los subproblemas, solo calcula los subproblemas que necesita para la solución final eliminando por completo algunos subproblemas.

En el enfoque ascendente, calcula todos los subproblemas, ya sea que se usen en la solución final o no. Esta diferencia puede no ser relevante en todos los problemas.

Un ejemplo que se me ocurre es el problema del cambio de monedas.
algoritmo de cambio de monedas

Aquí, utilizando DP, calcula toda la solución para todos los valores desde 1 hasta el valor para el que se necesita la solución.

Usando la recursividad para el mismo valor, calcularía soluciones solo para algunos de los subproblemas.

La programación dinámica es un método para resolver un problema complejo dividiéndolo en una colección de subproblemas más simples. Es aplicable a problemas que exhiben las propiedades de subproblemas superpuestos y una subestructura óptima. Donde as Backtracking es un refinamiento del enfoque de fuerza bruta, que busca sistemáticamente una solución a un problema entre todas las opciones disponibles.

El camino más corto en un gráfico, la secuencia de Fibonacci con memorización, los problemas de cambio de monedas se pueden resolver usando DP. Debido a que pueden dividirse en problemas más pequeños, y cada problema más pequeño tendrá tantas opciones, elegiremos el óptimo en cada nivel.

Los problemas de Sudoku, N Queen, conjunto de todas las palabras que se pueden formar usando un conjunto de caracteres, es decir, los problemas relacionados con la combinación se pueden resolver usando Backtracking.

La programación dinámica es solo recursividad más un poco de sentido común. La recursión significa que usted expresa el valor de una función en términos de otros valores de esa función (o como un caso base fácil de procesar). El sentido común es que implementa su función de tal manera que las llamadas recursivas se realizan por adelantado y se almacenan para facilitar el acceso.

Permítanme ilustrar con un ejemplo. Aquí hay dos funciones para calcular coeficientes binomiales; el primero usa recursividad, el segundo usa programación dinámica.

Recursividad:
int binom (int a, int b) {
if (b == 0 || b == a) devuelve 1;
de lo contrario, devuelve binom (a-1, b-1) + binom (a-1, b);
}

Programación dinámica:
int binomDP (int a, int b) {
int binom [a + 1] [a + 1];
para (int i = 0; i <= a; i ++) {
para (int j = 0; j <= i; j ++) {
si (j == 0 || j == i) binom [i] [j] = 1;
de lo contrario binom [i] [j] = binom [i-1] [j-1] + binom [i-1] [j];
}
}
devolver binom [a] [b];
}

Como puede ver, ambas funciones hacen exactamente lo mismo, exactamente de la misma manera. Pero el segundo es mucho más rápido (a expensas de usar mucha más memoria), porque las “llamadas recursivas” suceden en tiempo constante (solo acceden a una matriz).

Ambos son completamente diferentes, aunque puede encontrar casos en los que puede evitar las llamadas recursivas simplemente almacenando los resultados de las llamadas recursivas anteriores, evitando así una llamada a la función intercambiando algo de memoria. Por ejemplo, número de Fibonacci. ver la respuesta de Aashish Barnwal.

• La solución recursiva donde un subproblema se resuelve más de una vez, se puede hacer que funcione más rápido utilizando la técnica DP.
• No hay necesidad de DP en soluciones recursivas en las que no tiene que resolver el mismo subproblema más de una vez. Por ejemplo, búsqueda binaria.

La recursividad lo ayuda a descomponer su problema en subproblemas que son más fáciles de resolver.
La programación dinámica es una técnica en la que almacena el resultado del cálculo anterior para evitar calcularlo una vez más.

Como nota al margen, la programación dinámica es útil en casos donde el problema dado tiene una propiedad de subestructura óptima. Eso significa que se puede obtener un problema dado usando soluciones óptimas de sus subproblemas. por ejemplo, el problema del camino más corto.

Hay dos tipos de programación dinámica: de abajo hacia arriba y de arriba hacia abajo. Supongo que estás preguntando sobre esto último.

La programación dinámica de arriba hacia abajo es esencialmente recursiva, pero mejorada con la memorización . Usted ” memoriza ” los valores calculados en una tabla de búsqueda (generalmente una matriz), para evitar tener que volver a calcular esos valores nuevamente en el futuro; simplemente devuelve el valor en la tabla de búsqueda.

La principal diferencia es la superposición de subproblemas. La programación recursiva calculará los mismos subproblemas una y otra vez. Sin embargo, la programación dinámica busca el valor de un subproblema que se ha calculado en una tabla. En la práctica, suele ser más rápido.

La diferencia fundamental es el enfoque para resolver el problema.
En la recursión, usted divide el problema de arriba hacia abajo, pero en la programación dinámica lo aborda de abajo hacia arriba y también utiliza algún mecanismo para almacenar resultados intermedios.
La dificultad con la programación dinámica es que su solución no es muy obvia, hay que pensar de una manera muy diferente para entenderla.

El ejemplo más simple que se me ocurre es el cálculo factorial:
En la recursión para encontrar el Fac (n), desglosará el problema sabiendo que Fac (0) es 1

En la programación dinámica, comienza con Fac (0), luego lo almacena y lo usa para calcular Fac (1), etc.

Problemas similares que puede ver es Sub suma máxima del vector

La programación dinámica es un caso especial de recursión.

En la recursividad, si hay subproblemas que se resuelven repetidamente, almacena los resultados en lugar de volver a calcularlos. Este acto de recordar se llama Memoization. Toda esta técnica se llama programación dinámica.

La programación dinámica es un método para resolver problemas complejos dividiéndolos en pasos más simples. Es aplicable a problemas que exhiben las propiedades de subproblemas superpuestos que son solo una subestructura óptima ligeramente más pequeña.
Backtracking es un algoritmo general para encontrar todas (o algunas) soluciones a algún problema computacional, que construye gradualmente candidatos a las soluciones y abandona a cada candidato parcial c (“backtracks”) tan pronto como determina que c no puede completarse a un solución válida

Esta es la principal diferencia con la programación dinámica, que es exhaustiva y garantiza encontrar la solución. Después de cada etapa, la programación dinámica toma decisiones basadas en todas las decisiones tomadas en la etapa anterior, y puede reconsiderar la ruta algorítmica de la etapa anterior a la solución
Por ejemplo, supongamos que tiene que ir del punto A al punto B lo más rápido posible, en una ciudad determinada, durante la hora pico. Un algoritmo de programación dinámico analizará todo el informe de tráfico, analizará todas las combinaciones posibles de caminos que pueda tomar, y solo entonces le indicará cuál es el camino más rápido. Por supuesto, es posible que tenga que esperar un tiempo hasta que termine el algoritmo, y solo entonces puede comenzar a conducir. El camino que tomará será el más rápido (suponiendo que nada haya cambiado en el entorno externo).