Algoritmos recursivos y de retroceso
En el ámbito informático, muchos problemas se pueden resolver utilizando algoritmos recursivos. Entre los métodos recursivos, el más utilizado es el método de retroceso. Cuando analizamos el problema específicamente, podemos encontrar que la esencia de este tipo de problema es la forma del árbol.
La esencia del algoritmo recursivo es transformar el problema original en una versión más pequeña del mismo problema a resolver. Generalmente preste atención a dos puntos:
1. Condición de terminación recursiva. Correspondiente al problema más básico de los algoritmos recursivos, también es el problema más simple.
2. Proceso recursivo. El proceso recursivo implica empujar el problema original paso a paso hacia problemas idénticos más pequeños, donde más pequeños significan que los subproblemas son más fáciles de resolver. Hay algunos casos escritos donde se pueden encontrar fórmulas recursivas. Este proceso requiere una comprensión profunda del significado de las funciones recursivas. Ten claro cuáles son las entradas y salidas de esta función para que si las escribes quede mucho más claro.
Debido a esta fórmula recursiva, no nos resulta difícil encontrar que las condiciones de terminación de la recursividad son las conocidas f(0) y f(1). Con f(0) y f(1), podemos continuar derivando recursivamente f(3) hasta f(n).
Pero ahora estamos usando un algoritmo recursivo para resolver este problema:
Nuestras estructuras de datos comunes, como listas vinculadas, árboles, gráficos, etc. natural Dado que la lista vinculada tiene una estructura lineal, generalmente podemos resolver este problema directamente mediante bucles, ¡pero aquí usamos un método recursivo para resolverlo! Pregunta anterior de LeetCode
LeetCode 203 Eliminar elementos en una lista vinculada
Análisis: la estructura de una lista vinculada puede entenderse como un nodo que conecta una lista vinculada más corta y luego busca hacia abajo hasta el final Si un nodo es Ninguno, entonces el punto final de nuestra recursividad en este momento es apuntar al encabezado de Ninguno y devolver Ninguno
Después de comprender profundamente el algoritmo recursivo, comenzamos a aprender el método retroactivo . A través de las preguntas anteriores de LeetCode, comprendamos en profundidad la aplicación de la recursividad y el retroceso.
Actualizado continuamente...
Blog sobre estructura de datos y algoritmos:
I. Descripción general de la estructura de datos y algoritmos
II. Temas de arrays y LeetCode
III. Tablas vinculadas y problemas de LeetCode
IV.