Un procedimiento o función puede contener una llamada a otro procedimiento dentro de él. Incluso, la subrutina puede llamarse a sí misma. En este caso, a la computadora no le importa. Él, como siempre, ejecuta consistentemente los comandos que encuentra de arriba a abajo.
Si recuerdas las matemáticas, entonces allí puedes encontrar el principio de inducción matemática. Es como sigue: algún enunciado es verdadero para todo n natural si
1) es válido para n = 1;
2) de la validez de la declaración para cualquier natural arbitrario n = k se sigue que es verdadera para n = k+1.
En programación, esta técnica se llama recursividad.
Recursividad es una forma de definir un conjunto de objetos en términos del propio conjunto, basándose en casos base simples dados.
Recursivo es un procedimiento (función) que se llama a sí mismo directamente o a través de otros procedimientos y funciones.
Ejemplo de un procedimiento recursivo:
void Rec(int a)
{
si (a>0) { Rec(a-1); }
Consola.WriteLine(a);
}
Esquemáticamente, el trabajo de la recursividad se puede representar como un diagrama de flujo.
Rec() el procedimiento se ejecuta con el parámetro 3 Luego, dentro del procedimiento con parámetro 3, se llama al procedimiento con parámetro 2, y así sucesivamente, hasta que se llama al procedimiento con parámetro 0. trabajo. Luego, el control se transfiere nuevamente al procedimiento con el parámetro 1, también termina su trabajo imprimiendo el número 1, y así sucesivamente. antes del procedimiento con el parámetro 3.
Todos los procedimientos llamados se almacenan en la memoria hasta que completan su trabajo. El número de procedimientos simultáneos se denomina profundidad de recurrencia.
|
Descubrimos que la recursividad es la ejecución repetida de comandos contenidos en una subrutina. Y esto, a su vez, es similar al trabajo del ciclo. Hay lenguajes de programación en los que la construcción de bucle está completamente ausente, por ejemplo, Prolog.
Intentemos simular el trabajo del bucle for.
El bucle for contiene una variable de contador de pasos. En una subrutina recursiva, dicha variable se puede pasar como parámetro.
//procedimiento LoopImitation() con dos parámetros
// primer parámetro – contador de pasos, segundo parámetro – número total de pasos
static void LoopImitation(int i, int n)
{
Console.WriteLine("Hola N" + i); // declaración que se repetirá para cualquier valor i
if (i < n) // hasta que el contador de bucle sea igual a n,
{
LoopImitation(i+1, n); // llamando a un nuevo procedimiento de instancia, con parámetro i+1 (ir al siguiente valor de i)
}
}
|
Recursión e iteración
Para comprender la recursividad, debe comprender la recursividad...
Iteración en programación - un pasode un proceso cíclico de procesamiento de datos.
A menudo, los algoritmos iterativos en el paso actual (iteración) utilizan el resultado de la misma operación o acción calculada en los pasos anteriores. Un ejemplo de tales cálculos es el cálculo de las relaciones de recurrencia.
Un ejemplo simple de un valor recursivo es el factorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
El cálculo del valor en cada paso (iteración) es \(N=N \cdot i\) . Al calcular el valor de \(N\), tomamos el valor ya almacenado \(N\).< br />
El factorial de un número también se puede describir usando la fórmula recurrente:
\(\begin{ecuación*} n!= \begin{casos} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casos} \end{ecuación*}\)
Puede notar que esta descripción no es más que una función recursiva.
Aquí, la primera línea ( \(n <= 1\)) es el caso base (condición de terminación de recursividad) y la segunda línea es la transición al siguiente paso. < br />
| Función factorial recursiva |
Algoritmo iterativo |
int static Factorial(int n){
si (n > 1)
devuelve n * Factorial(n - 1);
de lo contrario devuelve 1;
}
|
int x = 1;
para (int i = 2; i <= n; i++)
x = x * yo;
Console.WriteLine("%d", x);
|
Debe entenderse que las llamadas a funciones implican una sobrecarga adicional, por lo que un cálculo factorial no recursivo será un poco más rápido.
Conclusión: donde puede escribir un programa con un algoritmo iterativo simple, sin recursión, entonces necesita escribir sin recursión. Pero aun así, existe una gran clase de problemas en los que el proceso computacional se implementa solo mediante recursividad.
Por otro lado, los algoritmos recursivos suelen ser más comprensibles.
Traducción recursiva de un número de un sistema numérico a otro
En en algunas situaciones en los procedimientos, puede usar la palabra return sin un argumento; es decir, de hecho, el procedimiento aún no devuelve nada. ; return se utiliza para finalizar el descenso en los casos base de los valores de los parámetros que se repiten. Por ejemplo, un procedimiento que convierte un número de decimal a binario puede verse así:
static void printTwo(int n)
{
si (n == 0) regresa;
imprimirDos(n/2);
if (n % 2 == 0) Consola.Escribir(0);
else Console.Write(1);
}
|
Tarea
En el alfabeto de la lengua de la tribu "Tumba-Yumba"; cuatro letras: "K", "L", "M" y "N". Debe mostrar todas las palabras que constan de n letras que se pueden construir a partir de las letras de este alfabeto.
El problema es un problema normal de fuerza bruta que se puede reducir a un problema más pequeño.
Sustituiremos secuencialmente las letras por la palabra.
La primera posición de una palabra puede ser una de las 4 letras del alfabeto (K. L, M, N).
Pongamos la letra K primero. Luego, para obtener todas las variantes con la primera letra K, debe enumerar todas las combinaciones posibles de letras en las posiciones restantes de n - 1 y así sucesivamente. (ver imagen).
 Así, el problema se reduce a resolver cuatro problemas de longitud n - 1.
Iterar sobre n caracteres recursivamente
w[0]='K'; // iterar sobre los últimos caracteres L-1
w[0]='L'; // iterar sobre los últimos caracteres L-1
w[0]='M'; // iterar sobre los últimos caracteres L-1
w[0]='N'; // iterar sobre los últimos caracteres L-1
w - una cadena de caracteres que almacena la palabra de trabajo.
Así, tenemos recursividad. Podemos disponer la solución del problema en forma de procedimiento recursivo.
¿Queda por determinar cuándo terminará la recursividad? Cuando todos los caracteres están configurados, es decir, el número de caracteres configurados es n. En este caso, debe mostrar la palabra resultante en la pantalla y salir del procedimiento.
El programa C# se verá así.
// w - parámetro modificable (resultado de cadena)
// Al procedimiento TumbaWords se le pasa el alfabeto como cadena de caracteres,
// la palabra palabra y el número de caracteres ya establecidos (al principio – 0)
static void TumbaWords( cadena A, ref cadena w, int N )
{
if (N == w.Length) // w.Length - el número de caracteres en la cadena
{
// si ya se han establecido todos los caracteres en la palabra,
// entonces es necesario generar una cadena y finalizar el procedimiento
Consola.WriteLine(w);
devolver;
}
for ( int i = 0; i < w.Length; i ++ ) // si la condición anterior es falsa (es decir, no todos los caracteres están espaciados,
{
// si la condición anterior es falsa (es decir, no todos los caracteres están espaciados,
// luego en el bucle repasamos todos los caracteres del alfabeto y
// coloca alternativamente el carácter en el primer espacio libre
w += A[i];
TumbaPalabras(A, ref w, N+1);
w = w.Remove(w.Length - 1); // y luego elimine el último carácter agregado,
// para hacer una nueva palabra con el mismo prefijo
}
}
vacío estático principal ()
{
int n = Convert.ToInt32(Console.ReadLine());
palabra de cadena = "";
TumbaWords("KLMN", ref palabra, 0);
}
TENGA EN CUENTA que w es un parámetro mutable (cadena de resultado)!
|
|