¿Quién puede informarme sobre la recursividad y el retroceso de Pascal?

En términos generales, la recursividad requiere condiciones de contorno, un segmento de avance recursivo y un segmento de retorno recursivo. Cuando no se cumplen las condiciones de contorno, avanza recursivamente; cuando se cumplen las condiciones de contorno, regresa recursivamente. Por lo tanto, al considerar el uso de un algoritmo recursivo para escribir un programa, se deben cumplir dos puntos: 1) el problema se puede describir de forma recursiva 2) existen condiciones límite para el final de la recursividad;

El poder de la recursividad radica en definir infinitas colecciones de objetos con declaraciones finitas. Los programas escritos con pensamiento recursivo suelen ser muy concisos y fáciles de entender.

[Ejemplo 2] muestra las disposiciones en orden y postorden de un árbol binario. Descubra cómo se prioriza.

[Análisis] Al comparar las disposiciones en orden y posorden del árbol binario, se pueden encontrar el nodo raíz y los subárboles izquierdo y derecho. De manera similar, al comparar el orden inverso y el orden inverso del subárbol izquierdo, se puede encontrar el nodo raíz del subárbol izquierdo... Se puede ver que este problema se puede describir de forma recursiva. Cuando se encuentra el último nodo raíz, la recursividad no puede continuar, que es la condición límite para el final de la recursividad. Se puede ver que la idea de divide y vencerás suele estar implícita en los algoritmos recursivos. El proceso es el siguiente:

Programa Chu 01_3;

var z, h: string;

Proceso find(a, b: string);

Proceso find(a, b: string);

p>

Definir variables

s, l: entero

Inicio

l:=longitud (b);

Si l = 1, entonces escriba (b) {condiciones de contorno y segmento de retorno recursivo}

Otros

Iniciar {segmento directo recursivo}

escriba (b[ l]);

s:=pos(b[l],a);

Si s-1>0 entonces busque (copiar(a,1, s-1) , copy(b, 1, s-1)); {subárbol izquierdo recursivo}

Si l-s >0 entonces busque (copy(a, s+1, l-s) , copy(b, s, l-s)); {subárbol derecho recursivo}

Fin

Fin

Inicio

readln(z); >

readln(h);

Buscar(z, h);

Readln

Fin.

[Aplicación de la recursividad]

1. Recursión clásica

Por ejemplo, el problema de la Torre de Hanoi: recursividad clásica, el problema original contiene subproblemas. Algunos problemas o estructuras de datos se describen de forma recursiva, por lo que la recursividad es natural.

2. Recursividad y recursividad

Las relaciones recursivas se establecen utilizando la idea de recursividad, como la secuencia de Fibonacci en los conejos. Pero la recursividad es más simple porque no hay segmento de retorno y, a veces, se puede implementar directamente a través de un bucle.

Divide y vencerás

Muchos métodos de divide y vencerás provienen del pensamiento recursivo o del procesamiento recursivo de descomposición + fusión.

Retroceso

Es más natural utilizar el retroceso para resolver problemas de pequeña escala. Preste atención a guardar y restaurar el sitio antes y después de la recursividad, es decir, el problema de transformación correcto.

5. Programación dinámica

La naturaleza superpuesta de los subproblemas de programación dinámica es similar a la recursividad. La recursividad + modificación dinámica de tablas de búsqueda es una buena forma de crear modelos de programación dinámicos.

6. Otros

Otros simplemente no son fáciles de categorizar. Como procesamiento de expresiones, permutación y combinación, etc. Por cierto, es muy conveniente utilizar la recursividad para solucionar problemas de esquemas de impresión.

[Ejemplo 3] Encuentra el número total de formas de dividir un número entero n por la suma de k enteros positivos diferentes.

[Análisis] Este es un problema de programación dinámica. La ecuación dinámica es la siguiente:

f[i-1, j]+f[i, j-I]+1((. j mod I = 0)y(j div I = 1))

f[i,j]:= f[i-1,j](I>=j)

f[i-1,j]+f[i,j-i](de lo contrario)

s:=f(k,n-k)

Este problema se puede solucionar mediante recursividad de bucle También puedes considerar el uso de la recursividad para resolver este problema.

El proceso principal es el siguiente:

Opción 1:

Programa de trabajo (I, j: longint; var s: longint

var t: longint);

p>

Inicio

Si (i=1) o (j=1) entonces s:=1

Si no, si (i=0) o (j=0) Entonces s:=0

De lo contrario, comience

Si (j mod i=0) y (j div i=1), entonces

Inicio

Trabajo(i-1,j,s);

t:= s;

Trabajo(I,j-1,s);

s:= s+t+1;

Fin

si no (I & gt;=j) entonces

Trabajar (i-1, j)

En caso contrario empezar

Trabajar(i-1,j,s);

t:= s;

Trabajo( I, j-1, s);

s:= s+t

Fin

Fin

Opción 2: Procesar búsqueda (v,w,último:byte);

var i:byte;

Iniciar

Si w=0, luego inc(count )

Otros

Si w=1, entonces

Si v & gt=last entonces buscar(0, 0, 0) else

else for i:=último en v-1 para buscar (v-i, w-1, I

Fin

Se puede ver que el el programa 1 es largo y consume mucho espacio de pila; la segunda opción es más simple, utiliza menos espacio de pila y es más eficiente. Por tanto, también existe un problema de optimización utilizando algoritmos recursivos. La simplicidad del algoritmo afecta directamente la viabilidad y eficiencia del programa.

[Resumen]

La recursión hace que algunos problemas complejos sean más fáciles de manejar, especialmente cuando se aprende diseño de algoritmos y estructuras de datos. Sin embargo, cada vez que se ejecuta la recursividad, es necesario asignar espacio de pila para las variables locales y las direcciones de retorno, lo que reduce la eficiencia operativa y limita la profundidad de la recursividad. Por lo tanto, cuando sea necesario, solo se puede utilizar el pensamiento recursivo para resolver el problema y el programa se escribe de forma no recursiva.

El método de retroceso, también conocido como método heurístico, renuncia al límite en el tamaño del problema y enumera y prueba las soluciones al problema una por una en un orden determinado. Cuando descubra que la solución actual no puede tener solución, elija la siguiente solución. Si la solución actual no cumple con los requisitos del problema, continúe expandiendo la escala de la solución actual y continúe explorando. Si la solución actual cumple con todos los requisitos, es la solución al problema. Al retroceder, el proceso de abandonar el plan actual y buscar el siguiente plan se llama retroceder.

En términos generales, existen dos tipos de problemas que requieren la resolución de computadoras:

1. Problemas descritos con fórmulas matemáticas precisas o lenguaje algorítmico explícito. Por ejemplo, el cálculo de pi, factorial de varios dígitos, etc.

2. En el proceso de completar una cosa, hay varios pasos y cada paso tiene varias ramas posibles. Para completar la tarea con éxito, hay algunas reglas que se deben seguir, pero estas reglas no pueden describirse con precisión mediante fórmulas matemáticas o lenguaje.

Para el segundo tipo de problema, generalmente se utiliza el método exhaustivo o el método de retroceso para resolverlo. El método exhaustivo consiste en enumerar todas las posibilidades del problema una por una. El método de retroceso es una estrategia de control del método exhaustivo. Enumera las soluciones que pueden completar con éxito la tarea. Es un método exhaustivo innecesario y bien organizado. Algoritmo de búsqueda. La idea básica es: durante el proceso de búsqueda, dado que la solución no se puede resolver en el estado actual, es necesario volver al enlace anterior en el proceso de búsqueda y buscar una solución nuevamente.

¿Cómo aprender a retroceder para resolver problemas? Primero echemos un vistazo a cómo utilizar el método exhaustivo para resolver el problema: Para facilitar un análisis más detallado del problema, el siguiente es un ejemplo (problema de reinas):

Descripción del problema: coloque cuatro reinas sobre un tablero de ajedrez 4×4, para que no puedan atacarse entre sí. No puede haber varias reinas en la misma fila, columna o diagonal. ¿Cuántas maneras hay?

Método exhaustivo:

Enumera todas las posibilidades de las cuatro reinas en el tablero de ajedrez y luego decide si atacar al oponente una por una. El procedimiento es el siguiente.

Método retrospectivo:

A la hora de buscar soluciones, debemos considerarlas enlace por enlace. Cuando se han probado todas las soluciones en un determinado enlace pero no se ha encontrado ninguna solución adecuada, tenemos que volver al enlace anterior y continuar explorando soluciones inexploradas. El proceso es el siguiente:

Programa qi 16;

Definir variables

I, t, an: palabra;

co, bo: tipo booleano;

Respuesta: Bytes del array [1..4];

Constante

n = 4; CT = 4;

Inicio

t:= 0; an:= 0;

Repetir

Inc(t); a[t]:= 0;

Repetir

Inc(a[t]);

bo:= false;

co:= false;

Si a[t]>CT entonces bo:=true

De lo contrario, comience

co:=true;

para I:= t -1 abajo a 1 haz {Comparar fila por fila con la fila donde está colocada la reina}

Si (t-i=abs(a[t]-a[i]) o (a[t]= a[i ]), entonces

co:= false;

end;

si bo, entonces inicia dec(t); , pero no Si se encuentra una solución adecuada, regrese}

Si t=0 entonces co:= true;

Fin;

Hasta co;

Si t & gt=n entonces

Iniciar {resultado de salida}

inc(安);

Escribir (' # ', un , ' ' :10);

Para i:=1 an, escriba(chr(64+i),':',a[i],'');

Escribiendo

Fin

Hasta t = 0;

Si an=0, entonces writeln('sin respuesta');

Fin.