¿Qué es la recursión y cuándo debo usarla?

votos
121

Uno de los temas que parece surgir regularmente en listas de correo y discusiones en línea es el mérito (o la falta de él) de realizar un Grado en Informática. Un argumento que parece surgir una y otra vez para la parte negativa es que han estado codificando durante algunos años y nunca han utilizado la recursión.

Entonces la pregunta es:

  1. ¿Qué es la recursión?
  2. ¿Cuándo usaría la recursión?
  3. ¿Por qué la gente no usa la recursión?
Publicado el 06/08/2008 a las 03:29
fuente por usuario
En otros idiomas...                            


40 respuestas

votos
86

Hay una serie de buenas explicaciones de recursión en este hilo, esta respuesta es acerca de por qué no debería usarla en la mayoría de los lenguajes. * En la mayoría de las implementaciones de lenguaje imperativo más importantes (es decir, cada implementación principal de C, C ++, Basic, Python , Ruby, Java y C #) la iteración es muy preferible a la recursión.

Para ver por qué, recorra los pasos que utilizan los idiomas anteriores para llamar a una función:

  1. el espacio está tallado en la pila para los argumentos de la función y las variables locales
  2. los argumentos de la función se copian en este nuevo espacio
  3. control salta a la función
  4. el código de la función se ejecuta
  5. el resultado de la función se copia en un valor de retorno
  6. la pila se rebobina a su posición anterior
  7. el control vuelve a donde se llamaba la función

Hacer todos estos pasos lleva tiempo, generalmente un poco más de lo que se necesita para iterar a través de un bucle. Sin embargo, el verdadero problema está en el paso # 1. Cuando se inician muchos programas, asignan un solo trozo de memoria para su pila, y cuando se quedan sin esa memoria (a menudo, pero no siempre debido a la recursión), el programa falla debido a un desbordamiento de la pila .

Entonces, en estos idiomas, la recursión es más lenta y te hace vulnerable al colapso. Todavía hay algunos argumentos para usarlo. En general, el código escrito recursivamente es más corto y un poco más elegante, una vez que sepa cómo leerlo.

Existe una técnica que los implementadores de lenguaje pueden usar llamada optimización de llamada de cola que puede eliminar algunas clases de desbordamiento de pila. En pocas palabras: si la expresión de retorno de una función es simplemente el resultado de una llamada a función, entonces no necesita agregar un nuevo nivel a la pila, puede reutilizar la actual para la función a la que se llama. Lamentablemente, pocas implementaciones de lenguaje imperativas tienen incorporada una optimización de llamada final.

* Me encanta la recursividad. Mi lenguaje estático favorito no usa bucles en absoluto, la recursividad es la única forma de hacer algo repetidamente. Simplemente no creo que la recursión sea generalmente una buena idea en idiomas que no están ajustados para eso.

** Por cierto, Mario, el nombre típico de tu función ArrangeString es "join", y me sorprendería que tu lenguaje de elección no tenga ya una implementación del mismo.

Respondida el 06/08/2008 a las 06:09
fuente por usuario

votos
63

Inglés simple ejemplo de recursividad.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
Respondida el 04/05/2010 a las 17:38
fuente por usuario

votos
49

En el sentido de la informática más básica, la recursividad es una función que llama a sí mismo. Digamos que tiene una estructura de lista enlazada:

struct Node {
    Node* next;
};

Y desea saber cuánto tiempo una lista enlazada es que usted puede hacer esto con la recursividad:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Esto podría, por supuesto, hacerse con un bucle, así, pero es útil como una ilustración del concepto)

Respondida el 04/05/2010 a las 12:25
fuente por usuario

votos
46

Cada vez que una función se llama a sí mismo, creando un bucle, entonces eso es la recursividad. Como con cualquier cosa hay buenos usos y malos usos de la recursividad.

El ejemplo más simple es la recursión de cola en la última línea de la función es una llamada a sí misma:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Sin embargo, este es un ejemplo cojo, casi sin sentido, ya que puede ser fácilmente reemplazado por iteración más eficiente. Después de todo, la recursión sufre de sobrecarga de llamada de función, que en el ejemplo anterior podría ser sustancial en comparación con la operación en el interior de la propia función.

Así que toda la razón para hacer la recursividad en lugar de iteración debe ser para tomar ventaja de la pila de llamadas para hacer algunas cosas inteligentes. Por ejemplo, si se llama a una función varias veces con diferentes parámetros dentro del mismo bucle, entonces eso es una manera de lograr la ramificación . Un ejemplo clásico es el triángulo de Sierpinski .

introducir descripción de la imagen aquí

Puede dibujar uno de los muy sencilla con la recursividad, donde las ramas pila de llamadas en 3 direcciones:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Si intenta hacer lo mismo con la iteración Creo que encontrará que se necesita mucho más código de lograr.

Otros casos de uso común pueden incluir jerarquías que atraviesan los rastreadores, por ejemplo, sitios web, las comparaciones de directorio, etc.

Conclusión

En términos prácticos, la recursividad tiene más sentido cuando lo necesite ramificación iterativo.

Respondida el 04/05/2010 a las 14:33
fuente por usuario

votos
28

La recursión es un método para resolver problemas basados ​​en la mentalidad de dividir y vencer. La idea básica es tomar el problema original y dividirlo en instancias más pequeñas (más fáciles de resolver), resolver esas instancias más pequeñas (generalmente usando el mismo algoritmo de nuevo) y luego volver a unirlas en la solución final.

El ejemplo canónico es una rutina para generar el factorial de n. El factorial de n se calcula multiplicando todos los números entre 1 y n. Una solución iterativa en C # se ve así:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

No hay nada sorprendente acerca de la solución iterativa y debería tener sentido para cualquiera que esté familiarizado con C #.

La solución recursiva se encuentra al reconocer que la n-ésima Factorial es n * Hecho (n-1). O para decirlo de otra manera, si sabes cuál es un número Factorial particular, puedes calcular el siguiente. Aquí está la solución recursiva en C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

La primera parte de esta función se conoce como caso base (o, a veces, cláusula de guardia) y es lo que impide que el algoritmo se ejecute para siempre. Simplemente devuelve el valor 1 cada vez que se llama a la función con un valor de 1 o menos. La segunda parte es más interesante y se conoce como el Paso recursivo . Aquí llamamos al mismo método con un parámetro ligeramente modificado (lo disminuimos por 1) y luego multiplicamos el resultado con nuestra copia de n.

La primera vez que se encontró esto puede ser algo confuso, por lo que es instructivo examinar cómo funciona cuando se ejecuta. Imagina que llamamos FactRec (5). Ingresamos a la rutina, no somos recogidos por el caso base y así terminamos así:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Si volvemos a ingresar el método con el parámetro 4, la cláusula guard no nos detiene de nuevo y, por lo tanto, terminamos en:

// In FactRec(4)
return 4 * FactRec(3);

Si sustituimos este valor de retorno en el valor de retorno anterior obtenemos

// In FactRec(5)
return 5 * (4 * FactRec(3));

Esto debería darte una pista sobre cómo se llega a la solución final, por lo que realizaremos un seguimiento rápido y mostraremos cada paso en el camino hacia abajo:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Esa sustitución final ocurre cuando se desencadena el caso base. En este punto, tenemos una fórmula algrebraica simple para resolver que se relaciona directamente con la definición de Factoriales en primer lugar.

Es instructivo observar que cada llamada al método da como resultado la activación de un caso base o una llamada al mismo método donde los parámetros están más cerca de un caso base (a menudo llamado llamada recursiva). Si este no es el caso, el método se ejecutará para siempre.

Respondida el 06/08/2008 a las 03:54
fuente por usuario

votos
12

La recursividad es la solución de un problema con una función que llama a sí mismo. Un buen ejemplo de esto es una función factorial. Factorial es un problema de matemáticas donde factorial de 5, por ejemplo, es 5 * 4 * 3 * 2 * 1. Esta función resuelve este en C # para números enteros positivos (no probado - que puede haber un error).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
Respondida el 04/05/2010 a las 12:29
fuente por usuario

votos
9

Considere un viejo problema, bien conocida :

En matemáticas, el máximo común divisor (mcd) ... de dos o más números enteros no nulos, es el mayor número entero positivo que divide los números sin un resto.

La definición de mcd es sorprendentemente simple:

definición mcd

donde mod es el operador de módulo (es decir, el resto después de la división entera).

En Inglés, esta definición dice que el máximo común divisor de cualquier número y cero es ese número, y el máximo común divisor de dos números m y n es el máximo común divisor de n y el resto después de dividir m por n .

Si desea saber por qué esto funciona, consulte el artículo de Wikipedia sobre el algoritmo de Euclides .

Vamos a calcular mcd (10, 8) como un ejemplo. Cada paso es igual a la que se acaba antes de que:

  1. gcd (10, 8)
  2. gcd (10, 10 mod 8)
  3. gcd (8, 2)
  4. gcd (8, 8 mod 2)
  5. gcd (2, 0)
  6. 2

En el primer paso, 8 no es igual a cero, por lo que la segunda parte de la definición se aplica. 10 mod 8 = 2 porque 8 entra en 10 una vez con un resto de 2. En el paso 3, la segunda parte se aplica de nuevo, pero esta vez 8 mod 2 = 0 porque 2 se divide 8 sin resto. En el paso 5, el segundo argumento es 0, por lo que la respuesta es 2.

¿Se dio cuenta de que mcd aparece tanto en los lados izquierdo y derecho del signo igual? Un matemático diría que esta definición es recursiva porque la expresión que está definiendo se repite dentro de su definición.

definiciones recursivas tienden a ser elegante. Por ejemplo, una definición recursiva de la suma de una lista es

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

donde heades el primer elemento en una lista y tailes el resto de la lista. Tenga en cuenta que sumse repite dentro de su definición en el final.

Tal vez usted prefiere el valor máximo de una lista en su lugar:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Es posible definir la multiplicación de números enteros no negativos de forma recursiva para convertirlo en una serie de adiciones:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Si eso poco acerca de la transformación de la multiplicación en una serie de adiciones no tiene sentido, trata de la ampliación de algunos ejemplos sencillos para ver cómo funciona.

Combinar especie tiene una definición recursiva preciosa:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Definiciones recursivas están por todas partes si usted sabe qué buscar. Observe cómo todas estas definiciones tienen casos base muy sencillas, por ejemplo , gcd (m, 0) = m. El recursivas casos reducir poco a poco el problema para bajar a las respuestas fáciles.

Con este entendimiento, ahora se puede apreciar los otros algoritmos en el artículo de Wikipedia sobre la recursividad !

Respondida el 04/05/2010 a las 14:58
fuente por usuario

votos
9

La recursividad se refiere a un método que resuelve un problema por resolver una versión más pequeña del problema y entonces usar ese resultado más algún otro cálculo para formular la respuesta al problema original. Muchas veces, en el proceso de resolución de la versión más pequeña, el método va a resolver una versión más pequeña todavía del problema, y ​​así sucesivamente, hasta que se alcanza un "caso base", que es trivial para resolver.

Por ejemplo, para calcular un factorial para el número X, se puede representar como X times the factorial of X-1. Por lo tanto, el método de "recursivamente" para encontrar el factorial de X-1, y luego se multiplica por lo que tiene Xpara dar una respuesta final. Por supuesto, para encontrar el factorial de X-1, primero que va a calcular el factorial de X-2, y así sucesivamente. El caso base sería cuando Xes 0 ó 1, en cuyo caso se conoce a regresar 1ya 0! = 1! = 1.

Respondida el 04/05/2010 a las 12:26
fuente por usuario

votos
9
  1. Una función que se llama a sí misma
  2. Cuando una función puede descomponerse (fácilmente) en una operación simple más la misma función en una porción más pequeña del problema. Debo decir, más bien, que esto lo convierte en un buen candidato para la recursividad.
  3. ¡Ellas hacen!

El ejemplo canónico es el factorial que se ve así:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

En general, la recursión no es necesariamente rápida (la sobrecarga de la llamada a la función tiende a ser alta porque las funciones recursivas tienden a ser pequeñas, ver más arriba) y puede sufrir algunos problemas (¿alguien puede desbordar la pila?). Algunos dicen que tienden a ser difíciles de "corregir" en casos no triviales, pero realmente no creo en eso. En algunas situaciones, la recursividad tiene más sentido y es la manera más elegante y clara de escribir una función en particular. Cabe señalar que algunos lenguajes favorecen las soluciones recursivas y las optimizan mucho más (LISP viene a la mente).

Respondida el 06/08/2008 a las 03:35
fuente por usuario

votos
7

Una función recursiva es aquella que se llama a sí misma. La razón más común que he encontrado para usarlo es atravesando una estructura de árbol. Por ejemplo, si tengo un TreeView con casillas de verificación (creo que la instalación de un nuevo programa, página "elegir las características para instalar"), es posible que desee un botón "verificar todo" que sería algo como esto (pseudocódigo):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Por lo tanto, puede ver que el checkRecursively comprueba primero el nodo que se pasa, luego se llama a sí mismo para cada uno de los hijos de ese nodo.

Debes ser un poco cuidadoso con la recursión. Si ingresa en un bucle recursivo infinito, obtendrá una excepción de desbordamiento de pila :)

No puedo pensar en una razón por la cual las personas no deberían usarlo, cuando sea apropiado. Es útil en algunas circunstancias, y no en otras.

Creo que debido a que es una técnica interesante, algunos codificadores quizás terminen usándola más a menudo de lo que deberían, sin una justificación real. Esto le ha dado mala reputación a la recursividad en algunos círculos.

Respondida el 06/08/2008 a las 03:44
fuente por usuario

votos
5

La recursividad es una expresión hace referencia directa o indirectamente en sí.

Considere acrónimos recursivos como un simple ejemplo:

  • GNU significa GNU No es Unix
  • PHP es sinónimo de PHP: Hypertext Preprocessor
  • YAML significa YAML no esta Markup Language
  • VINO significa Wine Is Not an Emulator
  • VISA es sinónimo de Visa International Service Association

Más ejemplos en Wikipedia

Respondida el 04/05/2010 a las 12:56
fuente por usuario

votos
5

Aquí hay un ejemplo simple: cuántos elementos en un conjunto. (hay mejores formas de contar cosas, pero este es un buen ejemplo recursivo simple.)

Primero, necesitamos dos reglas:

  1. si el conjunto está vacío, el recuento de elementos en el conjunto es cero (¡duh!).
  2. si el conjunto no está vacío, el recuento es uno más el número de elementos en el conjunto después de eliminar un elemento.

Supongamos que tiene un conjunto como este: [xxx]. vamos a contar cuántos artículos hay.

  1. el conjunto es [xxx] que no está vacío, por lo que aplicamos la regla 2. el número de elementos es uno más el número de elementos en [xx] (es decir, eliminamos un elemento).
  2. el conjunto es [xx], por lo que aplicamos la regla 2 de nuevo: una + cantidad de elementos en [x].
  3. el conjunto es [x], que aún coincide con la regla 2: uno + número de elementos en [].
  4. Ahora el conjunto es [], que coincide con la regla 1: ¡el recuento es cero!
  5. Ahora que conocemos la respuesta en el paso 4 (0), podemos resolver el paso 3 (1 + 0)
  6. Del mismo modo, ahora que conocemos la respuesta en el paso 3 (1), podemos resolver el paso 2 (1 + 1)
  7. Y finalmente, ahora que conocemos la respuesta en el paso 2 (2), podemos resolver el paso 1 (1 + 2) y obtener el recuento de elementos en [xxx], que es 3. ¡Hurra!

Podemos representar esto como:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Cuando aplica una solución recursiva, generalmente tiene al menos 2 reglas:

  • la base, el caso simple que establece lo que sucede cuando has "agotado" todos tus datos. Esta suele ser una variación de "si no tiene datos para procesar, su respuesta es X"
  • la regla recursiva, que establece lo que sucede si todavía tienes datos. Por lo general, este es un tipo de regla que dice "haz algo para reducir el tamaño de tu conjunto de datos y vuelve a aplicar tus reglas al conjunto de datos más pequeño".

Si traducimos lo anterior a pseudocódigo, obtenemos:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Hay muchos ejemplos más útiles (atravesando un árbol, por ejemplo) que estoy seguro que otras personas cubrirán.

Respondida el 06/08/2008 a las 04:12
fuente por usuario

votos
5

La recursividad funciona mejor con lo que me gusta llamar "problemas fractales", donde se trata de algo grande que está hecho de versiones más pequeñas de esa gran cosa, cada una de las cuales es una versión aún más pequeña de lo más importante, y así sucesivamente. Si alguna vez tiene que atravesar o buscar algo como un árbol o estructuras idénticas anidadas, tiene un problema que podría ser un buen candidato para la recursión.

Las personas evitan la recurrencia por varias razones:

  1. La mayoría de las personas (yo incluido) reducen sus dientes de programación en programación procedimental u orientada a objetos en oposición a la programación funcional. Para tales personas, el enfoque iterativo (típicamente utilizando bucles) se siente más natural.

  2. Aquellos de nosotros que cortamos nuestra programación en programación procedural u orientada a objetos a menudo se les ha dicho que eviten la recursión porque es propensa a errores.

  3. A menudo nos dicen que la recursión es lenta. Llamar y regresar de una rutina repetidamente implica una gran cantidad de empujar y hacer estallar, que es más lento que un bucle. Creo que algunos lenguajes manejan esto mejor que otros, y es muy probable que esos lenguajes no sean aquellos en los que el paradigma dominante sea procedimental u orientado a objetos.

  4. Para al menos un par de lenguajes de programación que he usado, recuerdo haber escuchado recomendaciones de no usar la recursividad si supera una cierta profundidad porque su stack no es tan profundo.

Respondida el 06/08/2008 a las 04:12
fuente por usuario

votos
4

1.) Un método es recursivo si puede llamarse a sí misma; ya sea directamente:

void f() {
   ... f() ... 
}

o indirectamente:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Cuando usar recursión

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) La gente usa la recursividad sólo cuando es muy complejo para escribir código iterativo. Por ejemplo, las técnicas de recorrido de árbol como el orden previo, orden posterior se pueden hacer tanto iterativa y recursiva. Pero por lo general usamos recursivo debido a su simplicidad.

Respondida el 11/03/2014 a las 10:47
fuente por usuario

votos
4

Una declaración recursivo es aquel en el que se define el proceso de qué hacer a continuación como una combinación de las entradas y de lo que ya lo han hecho.

Por ejemplo, tome factorial:

factorial(6) = 6*5*4*3*2*1

Pero es fácil ver factorial (6) también es:

6 * factorial(5) = 6*(5*4*3*2*1).

Por lo general:

factorial(n) = n*factorial(n-1)

Por supuesto, lo complicado de la recursividad es que si se quiere definir las cosas en términos de lo que ya lo han hecho, es necesario que haya un lugar para empezar.

En este ejemplo, acabamos de hacer un caso especial mediante la definición de factorial (1) = 1.

Ahora lo vemos desde abajo hacia arriba:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Desde definimos factorial (1) = 1, se llega a la "parte inferior".

En términos generales, los procedimientos recursivos tienen dos partes:

1) La parte recurrente, que define algún procedimiento en términos de nuevas entradas combinadas con lo que has "ya hecho" a través del mismo procedimiento. (es decir factorial(n) = n*factorial(n-1))

2) Una parte de la base, que se asegura de que el proceso no se repite siempre dándole algún lugar para empezar (es decir factorial(1) = 1)

Puede ser un poco confuso para conseguir su cabeza en torno al principio, pero tan sólo mirar a un montón de ejemplos y todo debe venir juntos. Si desea una comprensión más profunda del concepto, estudiar la inducción matemática. Además, tenga en cuenta que algunos idiomas optimizan para las llamadas recursivas, mientras que otros no lo hacen. Es bastante fácil de hacer las funciones recursivas increíblemente lentos si no tiene cuidado, pero también hay técnicas para hacerlos performant en la mayoría de los casos.

Espero que esto ayude...

Respondida el 04/05/2010 a las 14:30
fuente por usuario

votos
4

Me gusta esta definición:
En la recursividad, una rutina resuelve una pequeña parte de un problema en sí, el problema se divide en trozos más pequeños, y luego llama a sí misma para resolver cada una de las piezas más pequeñas.

También me gusta Steve McConnell discusión de la recursividad en el código completo en el que critica los ejemplos utilizados en los libros de Ciencias de la Computación en la recursividad.

No usar recursividad para factoriales o números de Fibonacci

Un problema con los libros de texto de ciencias de la computación es que presentan ejemplos tontos de la recursividad. Los ejemplos típicos son el cálculo de un factorial o el cálculo de una secuencia de Fibonacci. La recursividad es una herramienta de gran alcance, y es realmente tonto para utilizarlo en cualquiera de esos casos. Si un programador que trabajaba para mí utilizar la recursividad para calcular un factorial, me gustaría contratar a alguien más.

Pensé que esto era un punto muy interesante para subir y puede ser una razón por la recursividad es a menudo mal entendido.

EDIT: Esto no era una excavación en la respuesta de Dav - No había visto que la respuesta cuando me envió este

Respondida el 04/05/2010 a las 12:29
fuente por usuario

votos
3

Un ejemplo: Una definición recursiva de una escalera es: una escalera consta de: - un solo paso y una escalera (recursión) - o sólo una única etapa (terminación)

Respondida el 04/05/2010 a las 14:34
fuente por usuario

votos
3

Bueno, eso es una definición bastante decente que tiene. Y Wikipedia tiene una buena definición también. Así que voy a añadir otra definición (probablemente peor) para usted.

Cuando la gente se refiere a "recursividad", por lo general están hablando de una función que han escrito que se llama varias veces hasta que se haga con su trabajo. Recursividad puede ser útil cuando se atraviesa jerarquías en las estructuras de datos.

Respondida el 04/05/2010 a las 12:27
fuente por usuario

votos
3

Para recurse en un problema resuelto: no hacer nada, ya terminaste.
Para recurse en un problema abierto: haga el siguiente paso, luego recurse en el resto.

Respondida el 06/08/2008 a las 04:32
fuente por usuario

votos
2

Esta es una vieja pregunta, pero quiero añadir una respuesta desde el punto de vista logístico (es decir, no desde el punto de vista o el punto de vista del rendimiento algoritmo de corrección).

Yo uso de Java para el trabajo, y Java no soporta la función anidada. Como tal, si yo quiero hacer recursividad, que podría tener que definir una función externa (que existe sólo porque mi código choca contra el dominio burocrático de Java), o podría tener que refactorizar el código completo (que realmente odio a hacer).

Por lo tanto, a menudo evitar una recursión, y la operación uso pila en su lugar, debido a la recursividad en sí es esencialmente una operación de pila.

Respondida el 30/08/2014 a las 11:09
fuente por usuario

votos
2

Una función recursiva es una función que contiene una llamada a sí mismo. A struct recursiva es una estructura que contiene una instancia de sí mismo. Se pueden combinar los dos como una clase recursiva. La parte clave de un tema recurrente es que contiene una instancia / llamada de la misma.

Considere dos espejos enfrentados entre sí. Hemos visto el efecto infinito limpio que hacen. Cada reflexión es una instancia de un espejo, que está contenido dentro de otro ejemplo de un espejo, etc. El espejo que contiene un reflejo de sí es recursión.

Un árbol de búsqueda binaria es un buen ejemplo de programación de la recursividad. La estructura es recursiva con cada nodo que contiene 2 casos de un nodo. Funciones para trabajar en un árbol binario de búsqueda también son recursivos.

Respondida el 04/05/2010 a las 17:46
fuente por usuario

votos
2

En la llanura Inglés: Suponga que usted puede hacer 3 cosas:

  1. Tome una manzana
  2. Anote marcas de conteo
  3. Contar marcas de conteo

Usted tiene un montón de manzanas en frente de usted en una mesa y desea saber cuántas manzanas hay.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

El proceso de repetir lo mismo hasta que haya terminado se llama recursividad.

Espero que esta es la respuesta "simple Inglés" que busca!

Respondida el 04/05/2010 a las 14:09
fuente por usuario

votos
1

La definición más simple de la recursividad es "autorreferencia". Una función que se refiere a sí mismo, es decir, llama a sí misma es recursivo. Lo más importante a tener en cuenta, es que una función recursiva debe tener un "caso base", es decir, una condición que hace que si es cierto que no llamar a sí mismo, y así terminar la recursividad. De lo contrario tendrá recursividad infinita:

recursividad http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

Respondida el 04/05/2010 a las 17:10
fuente por usuario

votos
1

La recursividad es cuando se tiene una operación que utiliza la misma. Es probable que tenga un punto de parada, de lo contrario sería seguir para siempre.

Digamos que usted desea buscar una palabra en el diccionario. Usted tiene una operación llamada "mirar hacia arriba" a su disposición.

Su amigo dice "Realmente podría cuchara hasta un poco de pudín en este momento!" Usted no sabe lo que significa, por lo que mirar hacia arriba "cuchara" en el diccionario, y dice algo como esto:

Cuchara: sustantivo - un utensilio con una bola redonda en el extremo. Cuchara: verbo - para usar una cuchara en algo cuchara: verbo - abrazar estrechamente desde atrás

Ahora, siendo que en realidad no eres bueno con Inglés, esto le apunta en la dirección correcta, pero se necesita más información. Así se selecciona "utensilio" y "abrazo" a mejorar para algo más de información.

Abrazo: verbo - Utensilios para acurrucarse: sustantivo - una herramienta, a menudo un utensilio para comer

¡Oye! Usted sabe lo que es acurrucarse, y no tiene nada que ver con el pudín. También sabe que el pudín es algo que come, así que tiene sentido ahora. Su amigo debe querer comer con leche con una cuchara.

Bueno, bueno, este fue un ejemplo muy cojo, pero ilustra (tal vez poco) las dos partes principales de la recursividad. 1) Se utiliza en sí. En este ejemplo, usted no ha mirado realmente una palabra significativa hasta que entienda, y que eso podría significar mirando hacia arriba más palabras. Esto nos lleva al punto dos, 2) Se detiene en algún lugar. Tiene que tener algún tipo de caso base. De lo contrario, usted acaba de terminar mirando hacia arriba cada palabra en el diccionario, lo que probablemente no es demasiado útil. Nuestro caso base es que tienes suficiente información para hacer una conexión entre lo que previamente recibieron y no entiende.

El ejemplo tradicional que se da es factorial, donde 5 factorial es 1 * 2 * 3 * 4 * 5 (que es 120). El caso base sería 0 (o 1, dependiendo). Por lo tanto, para cualquier número entero n, hace lo siguiente

es n igual a 0? volver 1 en caso contrario, volver n * (factorial de n-1)

vamos a hacer esto con el ejemplo de 4 (que sabemos antes de tiempo es 1 * 2 * 3 * 4 = 24).

factorial de 4 ... ¿es 0? no, por lo que debe ser de 4 * factorial de 3, pero lo que es factorial de 3? es 3 * factorial de 2 factorial de 2 es 2 * factorial de 1 factorial de 1 es 1 * factorial de 0 y sabemos factorial de 0! -D es 1, que es el factorial definición de 1 es 1 * factorial de 0, que fue de 1 ... así que 1 * 1 = 1 factorial de 2 es 2 * factorial de 1, que fue de 1 ... así que 2 * 1 = 2 factorial de 3 es 3 * factorial de 2, que era 2 ... así 3 * 2 = 6 factorial de 4 (por fin !!) es 4 * factorial de 3, que era 6 ... 4 * 6 es 24

Factorial es un simple caso de "caso base, y utiliza a sí mismo".

Ahora, notamos que aún estaban trabajando en factorial de 4 todo el camino hacia abajo ... Si quisiéramos factorial de 100, nos gustaría tener que recorrer todo el camino hasta 0 ... que podría tener un montón de gastos generales a ella. De la misma manera, si nos encontramos con una palabra oscura para buscar en el diccionario, puede ser que tome mirando otras palabras y la exploración de las claves del contexto hasta que encontremos una conexión que estamos familiarizados. métodos recursivos pueden tomar mucho tiempo para trabajar su camino a través. Sin embargo, cuando se usan correctamente, y entendidas, pueden resolverse complicada sorprendentemente simple.

Respondida el 04/05/2010 a las 17:04
fuente por usuario

votos
1

Un gran número de problemas se pueden pensar en dos tipos de piezas:

  1. casos base, que son cosas elementales que se pueden resolver con sólo mirarlos, y
  2. casos recurrentes, que se basan en un problema mayor de piezas más pequeñas (elemental o de otro tipo).

Entonces, ¿qué es una función recursiva? Bueno, ahí es donde tiene una función que se define en términos de sí mismo, directa o indirectamente. OK, eso suena ridícula hasta que se da cuenta de que es razonable para los problemas de la clase descrita anteriormente: a resolver los casos base directamente y hacer frente a los casos recurrentes mediante el uso de las llamadas recursivas para resolver las piezas más pequeñas del problema incrustado dentro.

El ejemplo clásico de la verdad donde se necesita la repetición (o algo que huele muy parecido a él) es cuando usted está tratando con un árbol. Las hojas del árbol son el caso base, y las ramas son el caso recursivo. (En pseudo-C).

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

La forma más sencilla de imprimir esto con el fin de utilizar la recursividad es:

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

Está muerto fácil ver que eso va a trabajar, ya que es claro como el cristal. (El equivalente no recursivo es mucho más complejo, que requiere una estructura de pila interna para gestionar la lista de cosas para procesar.) Pues bien, en el supuesto de que nadie ha hecho una conexión circular por supuesto.

Matemáticamente, el truco para mostrar que la recursividad se doma es centrarse en la búsqueda de una métrica para el tamaño de los argumentos. Para nuestro ejemplo de árbol, la métrica más sencilla es la profundidad máxima del árbol debajo del nodo actual. En las hojas, es cero. En una rama con sólo deja por debajo de ella, que es uno, etc A continuación, puede simplemente mostrar que no ha ordenado estrictamente secuencia del tamaño de los argumentos que la función se invoca en el fin de procesar el árbol; los argumentos de las llamadas recursivas son siempre "menor" en el sentido de la métrica que el argumento de la llamada general. Con una métrica cardenal estrictamente decreciente, que está ordenada.

También es posible tener una recursión infinita. Eso es desordenado y en muchos idiomas no funcionará porque la pila explota. (En caso de que funcionara, el motor de lenguaje debe determinar que la función de algún modo no vuelve y es capaz, por tanto, para optimizar el mantenimiento de distancia de la pila de material Tricky en general;. Cola recursividad es sólo la forma más trivial de hacer esto .)

Respondida el 04/05/2010 a las 16:29
fuente por usuario

votos
1

La recursión es la técnica de definir una función, un conjunto o un algoritmo en función de sí misma.

Por ejemplo

n! = n(n-1)(n-2)(n-3)...........*3*2*1

Ahora se puede definir de forma recursiva como: -

n! = n(n-1)!   for n>=1

En términos de programación, cuando una función o método llama a sí mismo repetidamente, hasta que alguna condición específica se satisfizo, este proceso se llama recursividad. Pero tiene que haber una condición de terminación y la función o método no debe entrar en un bucle infinito.

Respondida el 04/05/2010 a las 16:22
fuente por usuario

votos
1

La recursividad en la informática es una técnica utilizada para calcular un efecto de resultado o lateral tras el retorno normal a partir de una única función (método, procedimiento o bloque) invocación.

La función recursiva, por definición debe tener la capacidad de invocar en sí ya sea directamente o indirectamente (a través de otras funciones) en función de una condición de salida o no se cumplan las condiciones. Si una condición de salida se encontró con los retornos particulares invocación a que la persona que llama. Esto continúa hasta que la invocación inicial se devuelve desde, momento en el que el efecto resultado o lado deseado estará disponible.

A modo de ejemplo, he aquí una función para realizar el algoritmo de ordenación rápida en Scala ( copiado de la entrada de Wikipedia para Scala )

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

En este caso, la condición de salida es una lista vacía.

Respondida el 04/05/2010 a las 15:14
fuente por usuario

votos
1

función llama a sí mismo o utilizar su propia definición.

Respondida el 04/05/2010 a las 14:59
fuente por usuario

votos
1

Cualquier algoritmo exhibe estructural recursividad en un tipo de datos si, básicamente, consiste en un interruptor de declaración con un caso para cada caso del tipo de datos.

por ejemplo, cuando se está trabajando en un tipo

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

un algoritmo recursivo estructural tendría la forma

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

esto es realmente la manera más obvia para escribir cualquier algorith que funciona en una estructura de datos.

Ahora, cuando nos fijamos en los números enteros (bueno, los números naturales) tal como se definen usando los axiomas de Peano

 integer = 0 | succ(integer)

se ve que un algoritmo recursivo estructural en números enteros se ve así

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

la función factorial demasiado bien conocido es sobre el ejemplo más trivial de esta forma.

Respondida el 04/05/2010 a las 14:53
fuente por usuario

votos
1

Hey, lo siento si mi opinión está de acuerdo con alguien, sólo estoy tratando de explicar la recursividad en la llanura Inglés.

supongamos que tiene tres gerentes - Jack, John y Morgan. Jack logra 2 programadores, John - 3, y Morgan - 5. vas a dar a cada gestor de 300 $ y quiere saber lo que costaría. La respuesta es obvia - pero lo que si 2 de los empleados de Morgan-s son también los gerentes?

Aquí viene la recursividad. empieza desde la parte superior de la jerarquía. el costo veraniega es 0 $. se inicia con Jack, a continuación, comprobar si tiene algún gerentes como empleados. si encuentra alguno de ellos es, comprobar si tienen alguna gerentes como empleados y así sucesivamente. Añadir 300 $ al coste de verano cada vez que se encuentra un gerente. cuando haya terminado con Jack, ve a Juan, sus empleados y luego a Morgan.

Nunca se sabrá, la cantidad de ciclos va a ir antes de recibir una respuesta, aunque saber cuántos gerentes que tiene y cuántos Presupuesto se puede gastar.

La recursividad es un árbol, con ramas y hojas, llamados padres e hijos respectivamente. Cuando se utiliza un algoritmo de recursividad, que más o menos consciente está la construcción de un árbol a partir de los datos.

Respondida el 04/05/2010 a las 13:50
fuente por usuario

votos
1

En la llanura Inglés, recursividad significa repetir calle detrás y otra vez.

En la programación es un ejemplo de llamar a la función en sí misma.

Mira el siguiente ejemplo de cálculo de factorial de un número:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
Respondida el 04/05/2010 a las 13:48
fuente por usuario

votos
1

La recursividad es el proceso en el que una llamada al método vacación por sí misma para poder realizar una tarea determinada. Reduce redundency de código. La mayoría de las funciones o métodos recurssive deben tener un condifiton para romper el recussive llamar es decir, evitar que se hace llamar si se cumple una condición - esto evita la creación de un bucle infinito. No todas las funciones son adecuados para ser utilizados de forma recursiva.

Respondida el 04/05/2010 a las 13:42
fuente por usuario

votos
1

es una manera de hacer las cosas una y otra vez indefinidamente de tal manera que se utiliza cada opción.

por ejemplo, si desea obtener todos los enlaces en una página HTML que se desea tener recurrencias porque cuando usted consigue todos los enlaces de la página 1 que se desea obtener todos los enlaces en cada uno de los enlaces que se encuentran en la primera página. a continuación, para cada enlace a un newpage usted quiere que los enlaces y así sucesivamente ... en otras palabras, es una función que llama a sí mismo desde el interior de sí mismo.

al hacer esto se necesita una manera de saber cuándo parar o de lo contrario se encontrará en un bucle sin fin para que agregue un parámetro entero a la función para realizar un seguimiento del número de ciclos.

en c # va a tener algo como esto:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
Respondida el 04/05/2010 a las 13:02
fuente por usuario

votos
1

"Si tengo un martillo, hacer que todo parezca como un clavo."

La recursividad es una estrategia de resolución de problemas para los enormes problemas, en los que a cada paso simplemente, "la curva 2 pequeñas cosas en una cosa más grande", cada vez con el mismo martillo.

Ejemplo

Supongamos que su escritorio está cubierto con un lío desorganizado de 1024 papeles. ¿Cómo se hace una pila ordenada, limpia de papeles de la suciedad, utilizando la recursividad?

  1. Divide: Extender todas las hojas a cabo, por lo que tiene una sola hoja en cada una "pila".
  2. Conquistar:
    1. Dar la vuelta, poniendo cada hoja una encima de la otra hoja. Ahora tiene pilas de 2.
    2. Dar la vuelta, poniendo cada uno 2-pila en la parte superior de otro 2-pila. Ahora tiene pilas de 4.
    3. Dar la vuelta, poniendo cada una 4-pila en la parte superior de otro 4-pila. Ahora tiene pilas de 8.
    4. ... incesantemente ...
    5. Ahora tiene una enorme pila de hojas de 1024!

Observe que esto es bastante intuitiva, además de contar todo (que no es estrictamente necesario). Es posible que no ir todo el camino hasta las pilas de hojas 1, en la realidad, pero se podía y todavía iba a funcionar. La parte importante es el martillo: Con los brazos, siempre se puede poner una pila en la parte superior de la otra para hacer una pila más grande, y no importa (dentro de lo razonable) cuán grande sea la pila es.

Respondida el 04/05/2010 a las 12:54
fuente por usuario

votos
1

Recursividad como se aplica a la programación está básicamente llamando a una función desde el interior de su propia definición (dentro de sí mismo), con diferentes parámetros con el fin de realizar una tarea.

Respondida el 04/05/2010 a las 12:25
fuente por usuario

votos
1

Desea usarlo cada vez que tenga una estructura de árbol. Es muy útil para leer XML.

Respondida el 21/08/2008 a las 14:18
fuente por usuario

votos
1

Mario, no entiendo por qué usaste recursión para ese ejemplo ... ¿Por qué no simplemente recorres cada entrada? Algo como esto:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

El método anterior sería más rápido y más simple. No es necesario utilizar recursión en lugar de un bucle simple. Creo que este tipo de ejemplos es la razón por la cual la recursión tiene una mala reputación. Incluso el ejemplo de función factorial canónica se implementa mejor con un bucle.

Respondida el 06/08/2008 a las 04:19
fuente por usuario

votos
0

En realidad, la mejor solución recursiva para factorial debería ser:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

Porque esta versión es Tail Recursive

Respondida el 21/08/2008 a las 14:39
fuente por usuario

votos
0

Yo uso recursión. ¿Qué tiene eso que ver con tener un título de CS ... (que, por cierto, no tengo)

Usos comunes que he encontrado:

  1. sitemaps - recurse a través del sistema de archivos que comienza en la raíz del documento
  2. arañas : rastreo a través de un sitio web para encontrar direcciones de correo electrónico, enlaces, etc.
  3. ?
Respondida el 06/08/2008 a las 04:13
fuente por usuario

votos
0

Creé una función recursiva para concatenar una lista de cadenas con un separador entre ellas. Lo uso principalmente para crear expresiones SQL, pasando una lista de campos como los " elementos " y una " coma + espacio " como separador. Esta es la función (utiliza algunos tipos de datos nativos de Borland Builder, pero se puede adaptar para adaptarse a cualquier otro entorno):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

Yo lo llamo de esta manera:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Imagine que tiene una matriz llamada ' campos ' con esta información dentro de ella: ' albumName ', ' releaseDate ', ' labelId '. Luego llamas a la función:

ArrangeString(fields, 0, ", ");

A medida que la función comienza a funcionar, la variable ' resultado ' recibe el valor de la posición 0 de la matriz, que es ' albumName '.

Luego verifica si la posición con la que está tratando es la última. Como no lo es, entonces concatena el resultado con el separador y el resultado de una función, que, oh Dios, es esta misma función. Pero esta vez, compruébalo, se llama agregar 1 a la posición.

ArrangeString(fields, 1, ", ");

Sigue repitiendo, creando una pila de LIFO, hasta que llega al punto donde la posición que se está tratando es la última, por lo que la función solo devuelve el elemento en esa posición de la lista, sin concatenar más. Entonces la pila se concatena hacia atrás.

¿Lo tengo? Si no lo haces, tengo otra manera de explicarlo. : o)

Respondida el 06/08/2008 a las 04:00
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more