La repetición, en las matemáticas y el de informática, es un método de definir las funciones en las cuales la función que es definida es aplicada dentro de su propia definición. El término también se utiliza más generalmente para describir un proceso de repetir objetos en una manera self-similar. Por ejemplo, cuando las superficies de dos espejos son casi paralelas a uno a las imágenes jerarquizadas que ocurren son una forma de repetición.

Definiciones formales de la repetición

En las matemáticas y el de informática, la repetición especifica (o las construcciones) una clase de objetos o de métodos (o de un objeto de cierta clase) definiendo algunos casos bajos muy simples o de los métodos (a menudo apenas uno), y definiendo reglas para analizar casos complejos en casos más simples.

Por ejemplo, lo que sigue es una definición recurrente de los antepasados de la persona:
Sus padres son sus antepasados (caso bajo );
Los padres de sus antepasados son también su antepasado (paso de la repetición del ).

Es conveniente pensar que una definición recurrente define objetos en términos de " previamente defined" objetos de la clase a definir.

Las definiciones tales como éstos se encuentran a menudo en matemáticas. Por ejemplo, la definición formal de los números naturales en teoría determinada es: 1 es un número natural, y cada número natural tiene un sucesor, que es también un número natural.

Aquí está otro, una manera quizás más simple entender procesos recurrentes: ¿

es nosotros hechos todavía? Si es así volver los resultados. Sin tal condición de la terminación del una repetición se encendería por siempre.

Si no, el simplifica el problema, soluciona los problemas más simples, y monta los resultados en una solución para el problema original. Entonces volver esa solución.

Una ilustración más chistosa va: " del ; Para entender la repetición, uno debe primero entender recursion." o quizás más exacto es el siguiente, Andrew Plotkin : " del ; Si usted sabe ya cuáles es la repetición, apenas recordar la respuesta. Si no, encontrar a alguien que se está colocando más cercano al Douglas Hofstadter que usted son; entonces preguntarle qué repetición is."

Los ejemplos de los objetos matemáticos definidos a menudo recurrentemente son los sistemas de las funciones y especialmente los fractales

Repetición en lengua

El uso de la repetición en la lingüística, y el uso de la repetición data generalmente del lingüista antiguo del indio Pāṇini en el siglo V A., que hizo uso de la repetición en sus reglas de la gramática sánscrito.

El Noam Chomsky del lingüista teoriza que la extensión ilimitada de una lengua tal como inglés es posible solamente por el dispositivo recurrente de encajar oraciones en oraciones. Así, una niña habladora puede decir, " del ; Dorothy, que encontró a bruja traviesa del oeste en la tierra de Munchkin en donde mataron a su hermana traviesa de la bruja, la liquidó con un cubo de water." claramente, &mdash simple de dos oraciones; " del ; Dorothy encontró a bruja traviesa del oeste en Munchkin Land" y " del ; Mataron a su hermana en Munchkin Land" &mdash de ; puede ser encajado en una tercera oración, " del ; Dorothy la liquidó con un cubo de agua, " para obtener una oración muy prolija.

Sin embargo, si " del ; Dorothy resolvió el Witch" travieso; se puede analizar como oración simple, entonces el " recurrente del de la oración; Él vivió en el built" de Gato de la casa; podría ser analizado que manera también, si " del ; Built" de Gato; se analiza como adjetivo, " del ; Gato-built", de que se aplica al " de la casa de la misma manera; Wicked" se aplica a la bruja. " del ; Él vivió en el house" Gato-construido; es inusual, el sonar quizás poético, sino no es claramente el incorrecto.

La idea que la repetición sea necesaria para la extensión ilimitada de una lengua es desafiada por el Daniel Everett del lingüista en sus apremios culturales del del trabajo en la gramática y la cognición en Pirahã: Otros miran las características del diseño de la lengua humana en las cuales él presume que los factores culturales hicieron la repetición innecesaria en el desarrollo de la lengua de Pirahã. Este concepto desafía la idea y la doctrina lingüística aceptada de Chomsky que la repetición es el único rasgo que distingue la comunicación humana y animal y está actual bajo discusión intenso.

Repetición en inglés llano

La repetición es el proceso que un procedimiento pasa por cuando uno de los pasos del procedimiento implica el volver a efectuar del entero el mismo procedimiento. Un procedimiento que pasa con la repetición reputa el recurrente. Algo también se dice ser el recurrente cuando es el resultado de un procedimiento recurrente.

Para entender la repetición, una debe reconocer la distinción entre un procedimiento y el funcionamiento de un procedimiento. Un procedimiento es un sistema de los pasos que deben ser tomados basado en un sistema de reglas. El funcionamiento de un procedimiento implica realmente siguiente las reglas y la ejecución de los pasos. Una analogía pudo ser que un procedimiento es como un menú en que es los pasos posibles, mientras que funcionar con un procedimiento está eligiendo realmente los cursos para la comida del menú.

Un procedimiento es recurrente si uno de los pasos que componga las llamadas de procedimiento para un nuevo funcionamiento del procedimiento. Por lo tanto una comida recurrente de cuatro cursos sería una comida en cuál de las opciones del aperitivo, de la ensalada, del entrée, o del postre era una comida entera a sí mismo. Tan una comida recurrente pudo ser pieles de patata, ensalada de verdes del bebé, parmesano del pollo, y para el postre, una comida de cuatro cursos, consistiendo en las tortas de cangrejo, la ensalada de Caesar, para un entrée, una comida de cuatro cursos, y la torta de chocolate para el postre, tan encendido hasta que cada uno de las comidas dentro de las comidas se termine.

Un procedimiento recurrente debe terminar todos de sus pasos. Incluso si un nuevo funcionamiento se llama en uno de sus pasos, cada uno que funciona debe funcionar con los pasos restantes. Cuál este los medios son que incluso si la ensalada es una comida entera de cuatro cursos a sí mismo, usted todavía tiene que comer su entrée y postre.

Humor recurrente

¡ ¡ Una broma común de Geeky (por ejemplo repetición en el archivo de la jerga) es el " siguiente; definition" de la repetición. El de la repetición del

l considera el " " de la repetición ;.

Otro ejemplo ocurre en el " de Kernighan y de Ritchie; La C que programa Language." La entrada de índice siguiente se encuentra en la página 269: repetición 86, 139, 141, 182, 202, 269 del

l del

Esto es un parodiar en referencias en los diccionarios, que en algunos casos descuidados pueden llevar a definiciones circulares que las bromas de tienen a menudo un elemento de la sabiduría, y también a un elemento del malentendido. Éste es también el ejemplo posible segundo-más corto de una definición recurrente errónea de un objeto, el error que es la ausencia de la condición de la terminación (o de carencia del estado inicial, si está mirado desde un punto de vista opuesto). Los recién llegado a la repetición desconcertar a menudo por su circularidad evidente, hasta que aprendan apreciar que una condición de la terminación es llave. Una variación es: el de la repetición del

l si usted todavía no lo consigue, considera: " " de la repetición ;.

qué hace realmente terminan, tan pronto como el " del lector; consigue el it".

Otros ejemplos son las siglas recurrentes tal como GNU, PHP o HURD .

Repetición en matemáticas

Sistemas recurrentemente definidos

Ejemplo: los números naturales

El ejemplo canónico de un sistema recurrentemente definido es dado por los números naturales : el

1 del está en
del $\backslash \; del\; mathbb\; \{N\}$ si el n está en el $\backslash \; el\; mathbb\; \{N\}$, después el n + 1 está en
del $\backslash \; del\; mathbb\; \{N\}$ que el sistema de números naturales es el sistema más pequeño de números verdaderos que satisfacen las dos características anteriores.
Ejemplo del

: El sistema de asuntos accesibles verdaderos Otro ejemplo interesante es el sistema de todo el " verdadero; reachable" asuntos en un sistema axiomático .

si un asunto es un axioma, es un asunto accesible verdadero.
si un asunto se puede obtener de asuntos accesibles verdaderos por medio de reglas de inferencia, es un asunto accesible verdadero.
El sistema de asuntos accesibles verdaderos es el sistema más pequeño de asuntos accesibles que satisfacen estas condiciones.

Se llama este sistema “verdad asuntos accesibles” porque: en acercamientos non-constructive a las fundaciones de las matemáticas, el sistema de asuntos verdaderos es más grande que el sistema construido recurrentemente de los axiomas y de las reglas de inferencia. Ver también los teoremas del estado incompleto de Gödel.

(Nota que determinando si cierto objeto está en un sistema recurrentemente definido no es una tarea algorítmica.)

Repetición funcional

Una función se puede definir en parte en términos de sí mismo. Un ejemplo familiar es la secuencia del número de Fibonacci : F ( n ) = F (&minus del n ; 1) + F (&minus del n ; 2). Para que tal definición sea útil, debe llevar a los valores que non-recursively se definen, en este caso al F (0) = 0 y al F (1) = 1.

Una función recurrente famosa es la función de Ackermann que, desemejante de la secuencia de Fibonacci, no se puede expresar sin la repetición.

Pruebas recurrentes

La manera estándar de definir nuevos sistemas de matemáticas o de lógica es definir objetos (tales como " true" y " false", o " todo el numbers" natural;), entonces definir las operaciones en éstos. Éstos son los casos bajos. Después de esto, todos los cómputos válidos en el sistema se definen con las reglas para montar éstos. De esta manera, si los casos bajos y las reglas todos se demuestran ser calculables, después cualquier fórmula en el sistema matemático también ser calculable.

Esto suena unexciting, pero este tipo de prueba es la manera normal de probar que un cálculo es imposible. Esto puede ahorrar a menudo mucho tiempo. Por ejemplo, este tipo de prueba fue utilizado para probar que el área de un círculo no es un cociente simple de su diámetro, y que el ningún ángulo puede ser trisected con el compás y la regla -- ambos rompecabezas que fascinaron a ancients.

Optimización recurrente

La programación dinámica es un acercamiento a la optimización que expone un multiperiod o un problema de varias fases de la optimización en forma modificada en forma recurrente. El resultado dominante en la programación dinámica es la ecuación de los botones, cuál escribe el valor del problema de la optimización en un rato anterior (o paso anterior) en términos de su valor en un rato posterior (o paso posterior).

Repetición en de informática

considera también:

la repetición (de informática)

Un método común de simplificación es dividir un problema en subproblemas del mismo tipo. Como técnica de la programación de computadora, esto se llama divisoria y conquista y es dominante al diseño de muchos algoritmos importantes, así como ser una parte fundamental de la programación dinámica .

La repetición en la programación de computadora se ejemplifica cuando una función se define en términos de sí mismo. Un uso del ejemplo de la repetición está en los programas de análisis para los lenguajes de programación. La gran ventaja de la repetición es que un sistema infinito de oraciones posibles, de diseños o de otros datos se puede definir, analizar o producir por un programa de computadora finito.

Las relaciones de repetición son ecuaciones para definir uno o más secuencias recurrentemente. Algunas clases específicas de relación de repetición pueden ser " solved" para obtener una definición no recurrente.

Un ejemplo clásico de la repetición es la definición de la función factorial, dada aquí en código de C:

lang=" del internacional sin firmar factorial (internacional sin firmar n) { si (vuelta 1 del <= de n 1); n de vuelta * factorial (n-1); }

Las llamadas de función sí mismo recurrentemente en una versión más pequeña de la entrada (n - 1) y multiplica el resultado de la llamada recurrente por n, hasta alcanzar la caja baja, análogo a la definición matemática de factorial.

El uso de la repetición en un algoritmo tiene ventajas y desventajas. La ventaja principal es generalmente simplicidad. La desventaja principal es a menudo que el algoritmo puede requerir granes cantidades de memoria si la profundidad de la repetición es muy grande. Se ha demandado que los algoritmos recurrentes son más fáciles de entender porque el código es más corto y está más cercano a una definición matemática, según lo considerado en estos ejemplos factoriales.

Es a menudo posible substituir una llamada recurrente por un lazo simple, como el ejemplo siguiente de demostraciones factoriales:

lang=" del internacional sin firmar factorial (internacional sin firmar n) { resultado sin firmar de la internacional = 1; si (vuelta 1 del <= de n 1); mientras que (n--) *= n del resultado; resultado de vuelta; }

Un ejemplo del algoritmo recurrente es el procedimiento que procesa (hace algo con) todos los nodos de una estructura de datos del árbol :

lang=" del ProcessTree vacío (nodo x) { internacional sin firmar i = 0; mientras que (i < x.count) { ProcessTree (x.children); i++; } ProcessNode (x); // ahora realiza la operación con el nodo sí mismo }

Para procesar el árbol entero, el procedimiento se llama con el nodo de raíz que representa el árbol como parámetro inicial. Las llamadas de procedimiento sí mismo recurrentemente en todos los nodos de niño del nodo dado (es decir sub-estructuras del árbol dado), hasta alcanzar la caja baja que es nodo sin los nodos de niño (es decir árbol que no tiene ninguna rama llamaron generalmente el " leaf").

La estructura de datos del árbol sí mismo se puede definir recurrentemente (y así que predestinated para el proceso recurrente) como esto:

lang=" del struct del typedef { cuenta sin firmar de la internacional; niños del node*; } nodo

El teorema de la repetición

En la teoría determinada, esto es un teorema que garantiza que existen las funciones recurrentemente definidas. Dado un sistema $X$, un elemento $a$ de $X$ y un $f\; de\; la\; función:\; X\; \backslash \; rightarrow\; X$, el teorema indica que hay un $F\; único\; de\; la\; función:\; N\; \backslash \; rightarrow\; X$ (donde $N$ denota el sistema de números naturales) tales que $F\; del\; (0)\; =$ F\; del$$
de a (n + 1) = f (F (n)) para cualquie número natural $n$.

Prueba de la unicidad

Tomar dos funciones $f$ y $g$ del dominio $N$ y del codomain $A$ tales que: $f\; del$

l (0) = $g\; del$
de a (0) = $f\; del$
de a (n + 1) = F $g\; del$
(de f (n)) (n + 1) = F (g (n))

donde está un elemento $a$ de $A$. Queremos probar ese $f\; =\; g$. Dos funciones son iguales si ellas: i del

l . tener dominios/codomains iguales; ii del
. tener el mismo gráfico. Inducción matemática : ¿para todo el $n$ en $N$, $f\; (n)\; =\; g\; (n)$? (Llamaremos este $Eq\; de\; la\; condición,\; por\; ejemplo,\; (n))$: del
1.$Eq\; (0)$ del
si y solamente si $f\; de\; (0)\; =\; g\; (0)$ si y solamente si $a\; =\; a$.Let $n$ sea un elemento de $N$. Si se asume que $Eq\; (n)$ se sostiene, nosotros quiere demostrar que $Eq\; (n\; +\; 1)$ se sostiene también, que es fácil porque: $f\; (n\; +\; 1)\; =\; F\; (f\; (n))\; =\; F\; (g\; (n))\; =\; g\; (n\; +\; 1)$. usted debe considerar la unión de N {0} como dominio de F.

Prueba de la existencia

Ver Hungerford, " Algebra", primer capítulo en teoría determinada.

----

Algunas relaciones de repetición comunes son:
factorial -- ¡$n!\; ¡=\; n\; (n\; -\; 1)!\; =\; n\; (n\; -\; 1)\; \backslash \; cdots\; 1$
Números de Fibonacci -- $f\; (n)\; =\; f\; (n\; -\; 1)\; +\; f\; (n\; -\; 2)$
El catalán numera -- $C\_0=1$, $C\_\; \{n+1\}\; =\; (4n+2)\; C\_n/(n+2)$

Interés compuesto computacional
La torre de Hanoi
Función de Ackermann
Tarifa del crecimiento demográfico
Probabilidades de un cumpleaños compartido entre un grupo de personas.

Ver también

Tesis de la Iglesia-Turing
Definición circular
Predicado continuo
repetición de los Curso-de-valores
Lengua decidible
Sistema decidible
Efecto de Droste
Programación dinámica
Combinator del punto fijo
Bucle infinito
Infinitism
Función iterada
Abyme del en de Mise
Función recurrente primitiva
Recursionism
Siglas recurrentes
Función recurrente
reentrante
Autorreferencia
Lazo extraño
Repetición de la cola
Torre de Hanoi
Lo completo de Turing
Tortugas hasta el final abajo de
Modelo de sistema viable

.

Zenithic

Cayman National Cultural Foundation

Random links:

Bill Clinton | Libro de Durrow | Raymond cambiante | Jämsänkoski | Río profundo (álbum)