Método recursivo de C#. Recursión. Tareas de formación. Brevemente sobre la recursividad
La recursividad es un fenómeno bastante común que ocurre no sólo en los campos de la ciencia, sino también en la vida cotidiana. Por ejemplo, el efecto Droste, el triángulo de Sierpinski, etc. La forma más sencilla de ver la recursión es apuntar la cámara web a la pantalla del monitor de la computadora, naturalmente, habiéndola encendido primero. Así, la cámara grabará la imagen de la pantalla del ordenador y la mostrará en esta pantalla, será algo así como un bucle cerrado. Como resultado, observaremos algo parecido a un túnel.
En programación, la recursividad está estrechamente relacionada con las funciones; más precisamente, es gracias a las funciones en programación que existe la recursividad o una función recursiva. En palabras simples, la recursividad es la definición de una parte de una función (método) a través de sí misma, es decir, es una función que se llama a sí misma, directamente (en su cuerpo) o indirectamente (a través de otra función). Típico problemas recursivos son las tareas: encontrar n!, números de Fibonacci. Ya hemos resuelto este tipo de problemas, pero utilizando bucles, es decir, de forma iterativa. En términos generales, todo lo que se resuelve de forma iterativa se puede resolver de forma recursiva, es decir, utilizando una función recursiva. Toda la solución se reduce a resolver el caso principal o, como también se le llama, base. Existe un paso recursivo o una llamada recursiva. En el caso en el que se llama a una función recursiva para resolver un problema complejo (no el caso base), se realizan una serie de llamadas o pasos recursivos para reducir el problema a uno más simple. Y así sucesivamente hasta llegar solución básica. ¡Desarrollemos un programa que declare una función recursiva que calcule n!
"stdafx.h" #incluir
corte
// código Código::Bloques
// código de desarrollo-C++
usando el espacio de nombres estándar; unsigned long int factorial(unsigned long int); // prototipo de una función recursiva int i = 1; // inicializando una variable global para contar el número de llamadas recursivas unsigned long int result; // variable global para almacenar el resultado devuelto de la función recursiva int main(int argc, char* argv) ( int n; // variable local para pasar el número ingresado desde el teclado cout EN El tipo de datos se declara unsigned long int , ya que el valor del factorial aumenta muy rápidamente, por ejemplo, ¡ya es 10! = 3.628.800. Si el tamaño del tipo de datos no es suficiente, el resultado será un valor completamente incorrecto. El código declara más operadores de los necesarios para encontrar n!. Esto se hace para que, después de ejecutarse, el programa muestre lo que sucede en cada paso de las llamadas recursivas. Tenga en cuenta las líneas de código resaltadas, líneas 23, 24, 28 es una solución recursiva para n!. Líneas 23, 24 son la solución básica de una función recursiva, es decir, tan pronto como el valor de la variable F será igual a 1 o 0 (ya que sabemos que 1! = 1 y 0! = 1), las llamadas recursivas se detendrán y se comenzarán a devolver los valores para cada llamada recursiva. Cuando regrese el valor de la primera llamada recursiva, el programa devolverá el valor del factorial calculado. EN línea 28 la función factorial() se llama a sí misma, pero su argumento es uno menos. El argumento se reduce cada vez para llegar a una solución particular. El resultado del programa (ver Figura 1).
Ingrese n!: 5 Resultado del Paso 1= 0 Resultado del Paso 2= 0 Resultado del Paso 3= 0 Resultado del Paso 4= 0 5!=120
Figura 1: recursividad en C++
Según el resultado del programa, cada paso es claramente visible y el resultado en cada paso es cero, excepto la última llamada recursiva. Fue necesario calcular cinco factoriales. El programa realizó cuatro llamadas recursivas y en la quinta llamada se encontró el caso base. Y una vez que el programa tuvo una solución para el caso base, resolvió los pasos anteriores y generó el resultado general. En la Figura 1, solo se ven cuatro pasos porque en el quinto paso se encontró una solución parcial, que finalmente arrojó la solución final, es decir, 120. La Figura 2 muestra el esquema de cálculo recursivo 5!. El diagrama muestra claramente que el primer resultado se devuelve cuando se alcanza una solución particular, pero no inmediatamente, después de cada llamada recursiva.
Figura 2 - Recursión en C++
¡Así que para encontrar 5! necesito saber 4! y multiplícalo por 5; 4! = 4*3! etcétera. Según el diagrama que se muestra en la Figura 2, el cálculo se reducirá a encontrar un caso especial, es decir, 1!, después del cual se devolverán los valores a cada llamada recursiva por turno. La última llamada recursiva devolverá el valor 5!.
Reelaboremos el programa para encontrar el factorial para obtener una tabla de factoriales. Para ello declararemos un bucle for en el que llamaremos a la función recursiva.
corte // código Código::Bloques // fibonacci.cpp: define el punto de entrada para la aplicación de consola. #incluir Digamos que necesitas mover tres discos de la primera varilla a la tercera, lo que significa que la segunda varilla es auxiliar. Una solución visual a este problema se implementa en Flash. Haga clic en el botón de inicio para iniciar la animación, en el botón de detener para detenerla. El programa debe escribirse para el enésimo número de discos. Dado que estamos resolviendo este problema de forma recursiva, primero debemos encontrar casos especiales de solución. En este problema, solo hay un caso especial: es cuando es necesario mover solo un disco y, en este caso, ni siquiera se necesita una varilla auxiliar, pero simplemente no le prestamos atención. Ahora es necesario organizar una solución recursiva si el número de discos es más de uno. Introduzcamos algo de notación para no escribir demasiado: <Б>
— la varilla sobre la que se ubican inicialmente los discos (barra base); Además, al describir el algoritmo para resolver el problema, utilizaremos estas notaciones. Para mover tres discos desde <Б>
en <Ф>
Primero debemos mover los dos discos de <Б>
en <П>
y luego mueva el tercer disco (el más grande) a <Ф>
, porque <Ф>
gratis para moverse norte discos con <Б>
en <Ф>
tenemos que movernos primero n-1 discos con <Б>
en <П>
y luego mueva el enésimo disco (el más grande) a <Ф>
, porque <Ф>
gratis Después de esto necesitas moverte. n-1 discos con <П>
en <Ф>
, mientras usa la varilla <Б>
como auxiliar. Estas tres acciones son todo el algoritmo recursivo. El mismo algoritmo en pseudocódigo: // hanoi_tower.cpp: define el punto de entrada para la aplicación de consola. // Un programa que resuelve recursivamente el problema de la Torre de Hanoi #include "stdafx.h" #include corte // código Código::Bloques corte int ayuda_rod; // bloque para determinar el número de varilla auxiliar, analizando los números de varilla inicial y final if (basic_rod != 2 && final_rod != 2) help_rod = 2; de lo contrario si (basic_rod! = 1 && final_rod! = 1) help_rod = 1; de lo contrario si (basic_rod! = 3 && final_rod! = 3) help_rod = 3;tower(// lanzando una función recursiva para resolver el problema de las Torres de Hanoi número, // una variable que almacena el número de discos que deben moverse basic_rod, // una variable que almacena el número de la varilla en la que se colocarán inicialmente los discos ubicado help_rod , // una variable que almacena el número de la varilla, que se utiliza como auxiliar final_rod); // variable que almacena el número de la varilla a la que se deben mover los discos return 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condición para finalizar llamadas recursivas ( cout La Figura 5 muestra un ejemplo del programa recursivo de la Torre de Hanoi. Primero ingresamos el número de discos igual a tres, luego ingresamos la varilla base (primera) y designamos la varilla final (tercera). Automáticamente la segunda varilla pasó a ser auxiliar. El programa produjo un resultado que coincide completamente con la solución animada a este problema. Un método recursivo es un método que directa o indirectamente se llama a sí mismo. Un método se llama indirectamente recursivo si contiene una llamada a otro método que contiene una llamada directa o indirecta al (primer) método definido. En el caso de recursividad indirecta, es posible que su recursividad no sea visible en el texto de la definición del método. Si el cuerpo de un método utiliza explícitamente una llamada a este método, entonces se produce recursividad directa. En este caso, se dice que el método es autoinvocado. Son los métodos autollamados los que llamaremos recursivos, y para los métodos con recursividad indirecta usaremos el término métodos indirectamente recursivos. Un ejemplo clásico de método recursivo es una función para calcular el factorial de un número entero no negativo. En C# se puede escribir de esta manera (programa 09_16.cs): hecho largo estático (int k) si(k< 0) return
0; si (k == 0 || k == 1) devolver k * hecho(k - 1); vacío estático Main09_16() Console.WriteLine("hecho(5)=" + hecho(5)); Para un argumento negativo, el resultado (por definición de factorial) no existe. En este caso, la función devuelve un valor nulo (podría devolver, por ejemplo, un valor negativo). Para un argumento cero y uno, por definición de factorial, el valor de retorno es 1. Si k >1, entonces se llama a la misma función con el valor del parámetro reducido en 1 y el valor que devuelve se multiplica por el valor actual del parámetro. k. Esto organiza el cálculo del producto. 1*2*3*.
..*(k-2)*(k-1)*
k.
Al diseñar un método recursivo, debe asegurarse Que pueda completar el trabajo, es decir. es imposible que se produzca un bucle; Que el método produzca resultados correctos. Para satisfacer el primer requisito se deben observar dos reglas: Debe haber una interrupción clara en la secuencia de llamadas recursivas, es decir, las autollamadas deben ejecutarse siempre que el valor de alguna expresión cuyos operandos cambien de una llamada a otra sea verdadero. Durante las autollamadas, deben ocurrir cambios en los parámetros y estos cambios después número finito Las llamadas deben dar lugar a una violación de la condición comprobada del párrafo 1. En nuestro ejemplo, la condición para salir de la cadena de llamadas recursivas es la verdad de la expresión (k==0 || k==1). Dado que el valor de k es finito y el parámetro disminuye en 1 con cada llamada posterior, la cadena de autollamadas es finita. Viniendo del final de la cadena, es decir. Desde 1 != 1, hasta el principio, puedes verificar que todas las llamadas funcionan correctamente y que el método en su conjunto funciona correctamente. Ilustración de una cadena de autollamadas para el hecho del método de cálculo factorial (4) La eficacia de un método recursivo suele estar determinada por la profundidad de la recursividad, es decir, el número de autollamadas en una cadena al llamar a un método. Como ejemplo de procedimiento recursivo, presentamos un método que convierte todos los dígitos de un número natural en sus símbolos correspondientes. Parámetros del método: tipo entero entero y una serie de caracteres de resultados. Texto del método (programa 09_17.cs): // Método de representación simbólica de dígitos de un número natural números vacíos estáticos (int n, char ch) int ind = (int)Math.Log10((doble)n); ch = (char)(n + (int)"0"); números(n/10, cap); ch = (char)(n % 10 + (int)"0"); vacío estático Main09_17() char ch = nuevo carbón; números(523, canal); Console.WriteLine("Numbers=" + new String(ch)); Limitación: al llamar a un método, es necesario que el tamaño del argumento-matriz de caracteres para representar los resultados sea al menos del tamaño del número. En el cuerpo del método, el valor de la variable ind es 1 menor que el tamaño de bits del valor numérico del argumento. entero norte. si norte<10,
то ind=O
и выполняются операторы c = (char)(n + (int)"0"); devolver; Operador devolver completa la ejecución de la siguiente instancia del procedimiento y, por lo tanto, interrumpe la cadena de sus autollamadas. De lo contrario, se ejecuta el operador números (n/10, ch); Se trata de una autollamada en la que el parámetro n se reduce 10 veces, es decir, se descarta el dígito menos significativo del número analizado. Tenga en cuenta que la declaración ch = (char)(n%10 + (int)"0"); no ejecutado: su ejecución se difiere hasta que se completa la llamada a números (n/10, ch). Y la finalización, es decir. La cadena de autollamadas se rompe cuando el valor del argumento es un número de un dígito. Este valor, el dígito más significativo del número original, se convierte a forma simbólica y se asigna al elemento ch[O]. Después de regresar de la llamada "más profunda" al método, se ejecuta la declaración ch = (char)(n%10 + (int)"0"); La variable n representa en este caso un número de dos dígitos y al elemento de la matriz ch se le asigna la imagen del segundo dígito (desde la izquierda) del número, etc. Muchos problemas que requieren repetición cíclica de operaciones pueden representarse mediante algoritmos recursivos e iterativos. Lo principal para un algoritmo recursivo es su autollamada, y para un algoritmo iterativo es un bucle. A modo de ilustración, presentamos un método (procedimiento) recursivo para mostrar los valores de los elementos de una matriz de caracteres en la pantalla de la consola. Recuerde que al crear una matriz de caracteres sin inicialización explícita, a sus elementos se les asignan los valores predeterminados "\0". Se muestran los elementos de la matriz, comenzando por el especificado. El final de la salida es el final de la matriz o el carácter terminal "\0" como valor del siguiente elemento (programa 09_17.cs). // Método para imprimir elementos de una matriz de caracteres chPrint vacío estático (char ch, int beg) if (beg >= ch.Longitud - 1 | ch == "\0") Consola.WriteLine(); Consola.Write(ch + " "); chPrint(ch, comenzar + 1); Primer parámetro del método carbonizarse ch: un enlace a la matriz de caracteres que se está procesando. Segundo parámetro entero beg es el índice del elemento a partir del cual se muestran los valores. La condición para salir del método es llegar al final del array beg >= ch.Length-1 o el valor "\0" del elemento con índice beg. Si no se cumple la condición de salida, se ejecutan las siguientes declaraciones: Consola.Write(ch + " "); chPrint(ch, comenzar + 1); Por lo tanto, el valor del elemento inicial de la matriz se muestra primero y se llama al método para el siguiente valor del segundo parámetro. Etc.... Llamar al último elemento distinto de \0 de la matriz completa la cadena de llamadas recursivas. Un ejemplo del uso de los métodos anteriores (09_17.cs): vacío estático Main09_17() símbolos de caracteres = nuevo carácter; números(13579, símbolos); chPrint(símbolos, 0); Resultado de la ejecución del programa: Tenga en cuenta que al llamar al método chPrint(), el segundo argumento es 0, es decir la salida proviene del comienzo de la matriz. Hola Habrahabr! En este artículo hablaremos sobre los problemas de recursividad y cómo solucionarlos. En programación, la recursividad está estrechamente relacionada con las funciones; más precisamente, es gracias a las funciones en programación que existe la recursividad o una función recursiva. En palabras simples, la recursividad es la definición de una parte de una función (método) a través de sí misma, es decir, es una función que se llama a sí misma, directamente (en su cuerpo) o indirectamente (a través de otra función). Se ha dicho mucho sobre la recursividad. Aquí hay algunos buenos recursos: de la red Cualquier algoritmo implementado en forma recursiva se puede reescribir en forma iterativa y viceversa. La pregunta sigue siendo si esto es necesario y qué tan efectivo será. Para justificar esto, se pueden dar los siguientes argumentos. Para empezar, podemos recordar las definiciones de recursividad e iteración. La recursividad es una forma de organizar el procesamiento de datos en la que un programa se llama a sí mismo directamente o con la ayuda de otros programas. La iteración es una forma de organizar el procesamiento de datos en la que ciertas acciones se repiten muchas veces sin dar lugar a llamadas recursivas al programa. Tras lo cual podemos concluir que son mutuamente intercambiables, pero no siempre con los mismos costes en términos de recursos y velocidad. Para justificar esto, podemos poner el siguiente ejemplo: hay una función en la que, para organizar un determinado algoritmo, hay un bucle que realiza una secuencia de acciones dependiendo del valor actual del contador (puede no depender de él). Dado que hay un ciclo, significa que el cuerpo repite una secuencia de acciones: iteraciones del ciclo. Puede mover operaciones a una subrutina separada y pasarle el valor del contador, si corresponde. Al finalizar la ejecución de la subrutina comprobamos las condiciones de ejecución del bucle, y si es verdadera procedemos a una nueva llamada a la subrutina, si es falsa completamos la ejecución; Porque Colocamos todo el contenido del bucle en una subrutina, lo que significa que la condición para ejecutar el bucle también se coloca en la subrutina, y se puede obtener a través del valor de retorno de la función, parámetros pasados por referencia o puntero a la subrutina. , así como variables globales. Además, es fácil demostrar que una llamada a una subrutina determinada desde un bucle se puede convertir fácilmente en una llamada o no llamada (devolver un valor o simplemente completar el trabajo) de una subrutina desde sí misma, guiada por algunas condiciones (aquellas que estaban previamente en la condición de bucle). Ahora, si observa nuestro programa abstracto, aproximadamente parece pasar valores a una subrutina y usarlos, que la subrutina cambiará cuando finalice, es decir. Reemplazamos el bucle iterativo con una llamada recursiva a una subrutina para resolver un algoritmo determinado. La tarea de llevar la recursividad a un enfoque iterativo es simétrica. En resumen, podemos expresar las siguientes ideas: para cada enfoque existe su propia clase de tareas, que está determinada por los requisitos específicos de una tarea específica. Puedes saber más sobre esto. Entonces la función recursiva consta de Solución de clase pública ( public static int recursion(int n) ( // condición de salida // Caso base // ¿cuándo dejar de repetir la recursión? if (n == 1) ( return 1; ) // Paso de recursión / condición recursiva return recursion( n - 1) * n; public static void main(String args) ( System.out.println(recursion(5)); // llamar a una función recursiva ) ) Aquí la condición básica es la condición cuando n=1. Ya que sabemos que 1!=1 y para calcular 1! no necesitamos nada. Para calcular 2! podemos usar 1!, es decir 2!=1!*2. Para calcular 3! necesitamos 2!*3... Para calcular n! ¡Necesitamos (n-1)!*n. Este es el paso de recursividad. En otras palabras, para obtener el valor factorial de un número n, basta con multiplicar el valor factorial del número anterior por n. Etiquetas: Agregar etiquetas Varg dice: Buenas tardes, realmente no puedo entender cómo esta función realiza los cálculos.
{ Según tengo entendido, en n hay 5, la condición no coincide, entonces este código se ejecuta suma(n-1)+n, es decir, algo obtenido entre paréntesis por resta se suma a 5, pero ¿qué es (5 - 1) + 5 y si es así, ¿qué detiene esta operación aritmética:?: :?: :?: ¿Cuál es el valor anterior, de dónde viene, a qué es igual:?: :?: :?: Sí, casi todo es como lo entendí (en el último párrafo mostraste recursividad))), pero la pregunta sigue siendo: ¿cómo se obtiene la suma, que luego se muestra en la pantalla? : (5) // Le dimos 5 a la función y verificamos su igualdad con uno. no es igual, llamó a la función nuevamente, pasándole 5-1 2-1 == 1, terminé de llamar a la función. Sí, sí, sí, no tuve tiempo de escribir, lo entendí, todo está correcto, algo no se entendió de inmediato. Gracias buen sitio)) Y todavía no es del todo lógico que en la octava línea, si cambia el número devuelto de 1 a 2, la cantidad cambia a 16. ¿Cómo se relaciona esta condición con la novena línea? :
<П>
- varilla auxiliar o intermedia;
<Ф>
— varilla final: la varilla a la que se deben mover los discos.
n-1 convidar a <П>
norte convidar a <Ф>
n-1 pasar de <П>
en <Ф>
, mientras usa <Б>
como auxiliarBrevemente sobre la recursividad
La recursividad es un fenómeno bastante común que ocurre no sólo en los campos de la ciencia, sino también en la vida cotidiana. Por ejemplo, el efecto Droste, el triángulo de Sierpinski, etc. Una forma de ver la recursividad es apuntar la cámara web a la pantalla del monitor de la computadora, naturalmente, habiéndola encendido primero. Así, la cámara grabará la imagen de la pantalla del ordenador y la mostrará en esta pantalla, será algo así como un bucle cerrado. Como resultado, observaremos algo parecido a un túnel.
Se supone que el lector está teóricamente familiarizado con la recursividad y sabe qué es. En este artículo prestaremos más atención a los problemas de recursividad. Tareas
Al aprender la recursividad, la forma más eficaz de comprender la recursividad es resolver problemas. ¿Cómo resolver problemas de recursividad?
En primer lugar, es necesario comprender que la recursividad es una especie de exageración. En términos generales, todo lo que se resuelve de forma iterativa se puede resolver de forma recursiva, es decir, utilizando una función recursiva.
Al igual que una enumeración (ciclo), la recursividad debe tener una condición de parada: caso base (de lo contrario, al igual que un ciclo, la recursividad funcionará para siempre: infinita). Esta condición es el caso al que va la recursividad (paso de recursividad). En cada paso, se llama a una función recursiva hasta que la siguiente llamada activa la condición base y la recursividad se detiene (o más bien, regresa a la última llamada a la función). Toda la solución se reduce a resolver el caso base. En el caso en el que se llama a una función recursiva para resolver un problema complejo (no el caso base), se realizan una serie de llamadas o pasos recursivos para reducir el problema a uno más simple. Y así sucesivamente hasta obtener una solución básica.
Veamos esto usando el ejemplo de encontrar el factorial:
si (n==1) devuelve 1; //si el nuevo valor es 1, entonces lo sumaremos con 1, y no con el anterior. porque el anterior es cero. y la suma 1+0 será infinita.
de lo contrario devolver suma(n-1)+n; //pero si n>1, entonces lo sumamos con el valor anterior igual a la suma de todos los elementos hasta n
}
Trabajo con Dev C++, este ejemplo muestra la cantidad ==15, si lo cuenta como está escrito en el ejemplo, entonces la cantidad resulta ser diferente.
Escribí arriba, tomemos (5-1)+5=4+5=9
1+2+3+4+5 = 15. El ejemplo genera correctamente.
(5-1+(5)) //...
(4-1+(5-1+(5)))
(3-1+(4-1+(5-1+(5))))
(2-1+(3-1+(4-1+(5-1+(5)))))
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
este es el resultado.
Aquí el resultado de la función es la diferencia de los dos primeros números y n es el resto del lado derecho.
__________________________________
Sólo necesita entender la función correctamente y aceptarla como un valor calculado y no entenderla como una variable. Es similar a una variable, pero más cercana a una constante calculada, aunque no es una constante, simplemente es más conveniente percibirla así.
Con esto también todo está claro, simplemente devolver 2 suma su privación a la suma, por así decirlo.
no la estrella extra, sino estas dos, y si escribes -3, entonces al sumar una vez restará las tres, etc.
Toda la lógica es que cualquier función recursiva necesita un punto de retorno.
La conexión con la novena línea es que se pasa un número a la función de suma cuando se llama desde dentro de main durante llamadas recursivas, este número se reduce en uno (n-1) cada vez, se verifica este resultado n-1; igualdad con uno y si la igualdad es verdadera, entonces el monto total recibido se sumará con el número de esa declaración. de lo contrario, el total total se sumará con este nuevo n-1
