¿Cómo podemos comprender profundamente la recursividad y el retroceso?

La recursión es una estructura algorítmica, y el retroceso es una idea algorítmica. Una recursión es llamar a la función misma en una función para resolver un problema. El retroceso es generar una solución al problema a través de diferentes intentos. es algo similar a la enumeración de pobreza, pero a diferencia de la enumeración exhaustiva, retroceder "podará", lo que significa que no es necesario enumerar las siguientes respuestas para los resultados que ya se sabe que son incorrectos, como una secuencia ordenada de 1, 2, 3, 4, 5. Para encontrar todos los conjuntos cuya suma es 5, busqué de adelante hacia atrás y seleccioné 1, luego 2 y luego 3. Cuando descubrí que la suma ya era mayor de lo esperado, entonces 4 y 5. Definitivamente no funcionaría. Esta es una optimización del proceso de búsqueda.

El análisis retrospectivo es una de las características del seguimiento de decisiones. Se refiere al análisis del mecanismo original de toma de decisiones, el contenido de la toma de decisiones, el entorno subjetivo y objetivo, etc. Partiendo del punto de partida, examinamos secuencialmente las causas de los errores en la toma de decisiones, la naturaleza del problema, el alcance del error, etc.

[Análisis de algoritmos]

Para describir un determinado estado del problema se debe utilizar su estado anterior, y para describir el estado anterior se debe utilizar su estado anterior. ... Este método de definirse a uno mismo se llama definición recursiva. Por ejemplo: defina la función f(n) como:

f(n)=n*f(n-1) (ngt; 0)

f(n)=1 ( n =0)

Entonces, cuando 0, f(n) debe definirse por f(n-1), y f(n-1) debe definirse por f(n-1-1). .. Cuando Cuando n=0, f(n)=1.

Podemos ver en el ejemplo anterior que la definición recursiva tiene dos elementos:

(1) Condiciones de contorno recursivas. Es decir, el caso más simple del problema descrito, que ya no utiliza una definición recursiva.

Como en el ejemplo anterior, cuando n=0, f(n)=1 y f(n-1) no se utilizan para definir.

(2) Definición recursiva: regla que transforma el problema en condiciones de contorno. Las definiciones recursivas deben simplificar cada vez más el problema.

Como en el ejemplo anterior: f(n) se define por f(n-1), acercándose cada vez más a f(0), que es la condición de frontera. El caso más simple es f(0)=1.

La eficiencia de los algoritmos recursivos suele ser muy baja, lo que consume tiempo y espacio en la memoria. Sin embargo, la recursividad también tiene sus ventajas. Puede hacer que un programa que contiene relaciones recursivas y una estructura compleja sea más conciso y aumente la legibilidad. Cuando es difícil encontrar todo el proceso desde el límite hasta la solución, si el problema se lleva más lejos y el resultado aún mantiene la relación del problema original, es más apropiado utilizar la programación de algoritmos recursivos.

La recursividad se divide en: 1. Recursión directa, el proceso recursivo P se llama a sí mismo directamente 2. Recursión indirecta, es decir, P contiene otro proceso D y D llama a P.

Las situaciones generales en las que Los algoritmos recursivos aplicables son:

1. La forma de definición de los datos se define de forma recursiva.

Por ejemplo, la definición de la secuencia de Pebonacci: f(n)=f( n-1) f(n-2); f (0)=1; f(1)=2.

El programa recursivo correspondiente es:

Función fib(n: entero): entero;

Comenzar

si n = 0 entonces fib := 1 {límite de recursión}

de lo contrario, si n = 1 entonces fib := 2

else fib := fib (n-2) fib(n-1) {Recursion}

End;

Este tipo de problema recursivo se puede convertir en un algoritmo recursivo, y el límite recursivo se utiliza como condición de límite de la recursividad

2. La relación entre los datos (es decir, la estructura de datos) se define de forma recursiva. .

3. La solución del problema se implementa de acuerdo con el algoritmo recursivo, por ejemplo, el método de retroceso, etc.

Comience desde una determinada posibilidad del problema y busque todas las posibilidades que puedan existir. logrado a partir de esta situación. Cuando este camino llegue al "final"

Cuando llegue el momento, regrese al punto de partida, comience desde otra posibilidad y continúe buscando este método de "retroceder" constantemente para encontrar. una solución se llama

"método de retroceso".

[Programa de referencia]

El marco del algoritmo para encontrar todas las rutas utilizando el método de retroceso se proporciona a continuación. los comentarios se han escrito con mucha claridad, por favor entiéndalo con atención.

Const max Depth = ;

Tipo statetype = ?; {definición de tipo de estado}

operatertype = ? ; {definición de tipo de operador}

nodo = Registro {tipo de nodo}

estado: tipo de estado; {campo de estado}

operador: tipo de operador {campo de operador}

Fin;

{ Nota: El tipo de datos del nodo puede basarse en Las preguntas de la prueba deben simplificarse}

Var

pila: Matriz [1..maxprofundidad] del nodo; {guardar la ruta actual}

total: entero; {número de rutas}

Procedimiento make(l: entero);

Var i: entero;

Comenzar

si la pila[L-1] es el nodo objetivo, entonces

Comenzar

total: = total 1; {Número de rutas 1}

Imprimir la ruta actual [1..L-1]

Salir