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

recursividad en estructura de datos pdf (30)

Uno de los temas que parece surgir regularmente en las listas de correo y las discusiones en línea es el mérito (o la falta de ellos) de obtener un título en ciencias informáticas. Un argumento que parece surgir una y otra vez para la parte negativa es que han estado codificando durante varios años y nunca han usado la recursión.

Así que la pregunta es:

¿Qué es la recursión?
¿Cuándo usaría la recursión?
¿Por qué la gente no recurre?

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

El ejemplo canónico es el factorial que se parece a:

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 de función tiende a ser alta porque las funciones recursivas tienden a ser pequeñas, ver más arriba) y pueden sufrir algunos problemas (¿desbordamiento de pila en alguien)? Algunos dicen que tienden a ser difíciles de "acertar" en casos no triviales, pero realmente no me gusta. En algunas situaciones, la recursión tiene más sentido y es la forma más elegante y clara de escribir una función en particular. Cabe señalar que algunos idiomas favorecen las soluciones recursivas y las optimizan mucho más (LISP viene a la mente).

La función se llama a sí misma o usa su propia definición.

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

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

o indirectamente:

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

2.) Cuándo usar la 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 recursión solo cuando es muy complejo escribir código iterativo. Por ejemplo, las técnicas de recorrido de árboles como preorden, postorder pueden hacerse iterativas y recursivas. Pero usualmente usamos recursivo por su simplicidad.

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

Primero, necesitamos dos reglas:

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

Supongamos que tienes un conjunto como este: [xxx]. contemos cuántos elementos hay.

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).
el conjunto es [xx], por lo que aplicamos la regla 2 nuevamente: uno + número de elementos en [x].
el conjunto es [x], que aún coincide con la regla 2: uno + número de elementos en [].
Ahora el conjunto es [], que coincide con la regla 1: ¡el conteo es cero!
Ahora que conocemos la respuesta en el paso 4 (0), podemos resolver el paso 3 (1 + 0)
Del mismo modo, ahora que conocemos la respuesta en el paso 3 (1), podemos resolver el paso 2 (1 + 1)
Y finalmente, ahora que sabemos 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

Al aplicar una solución recursiva, generalmente tiene al menos 2 reglas:

la base, el caso simple que establece lo que sucede cuando ha "agotado" todos sus datos. Esto suele ser una variación de "si no tienes datos para procesar, tu respuesta es X"
la regla recursiva, que establece lo que sucede si aún tiene datos. Por lo general, este es un tipo de regla que dice "haga algo para reducir su conjunto de datos y vuelva a aplicar sus 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 (atravesar un árbol, por ejemplo) que estoy seguro que otras personas cubrirán.

Bueno, esa es una definición bastante decente que tienes. Y la wikipedia tiene una buena definición también. Así que añadiré otra definición (probablemente peor) para ti.

Cuando las personas se refieren a la "recursión", generalmente hablan de una función que han escrito que se llama a sí misma repetidamente hasta que termina con su trabajo. La recursión puede ser útil al atravesar jerarquías en estructuras de datos.

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

El ejemplo más simple es la recursión de la cola donde 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 poco convincente y sin sentido, ya que puede reemplazarse fácilmente por una iteración más eficiente. Después de todo, la recursión sufre una sobrecarga de llamada a la función, que en el ejemplo anterior podría ser sustancial en comparación con la operación dentro de la propia función.

Por lo tanto, la razón principal para hacer la recursión en lugar de la iteración debe ser aprovechar la pila de llamadas para hacer algunas cosas inteligentes. Por ejemplo, si llama a una función varias veces con diferentes parámetros dentro del mismo bucle, entonces esa es una manera de lograr la branching . Un ejemplo clásico es el triángulo de Sierpinski .

Puede dibujar uno de esos de manera muy simple con la recursión, donde la pila de llamadas se divide 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 intentas hacer lo mismo con la iteración, creo que encontrarás que se necesita mucho más código para lograrlo.

Otros casos de uso comunes pueden incluir jerarquías de desplazamiento, por ejemplo, rastreadores de sitios web, comparaciones de directorios, etc.

Conclusión

En términos prácticos, la recursión tiene más sentido siempre que necesite una ramificación iterativa.

Considere un problema viejo y bien conocido :

En matemáticas, el mayor divisor común (gcd) ... de dos o más enteros distintos de cero, es el mayor entero positivo que divide los números sin un resto.

La definición de gcd es sorprendentemente simple:

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 mayor divisor común de cualquier número y cero es ese número, y el mayor divisor común de dos números m y n es el mayor divisor común de n y el resto después de dividir m por n .

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

Vamos a calcular gcd (10, 8) como ejemplo. Cada paso es igual al que tiene justo antes:

gcd (10, 8)
gcd (10, 10 mod 8)
gcd (8, 2)
gcd (8, 8 mod 2)
gcd (2, 0)
2

En el primer paso, 8 no es igual a cero, por lo que se aplica la segunda parte de la definición. 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 divide 8 sin resto. En el paso 5, el segundo argumento es 0, por lo que la respuesta es 2.

¿Notaste que gcd aparece 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 recurs dentro de su definición.

Las definiciones recursivas suelen ser elegantes. Por ejemplo, una definición recursiva para la suma de una lista es

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

donde head es el primer elemento de una lista y tail es el resto de la lista. Tenga en cuenta que la sum repite dentro de su definición al final.

Quizás prefieras el valor máximo en 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

Puede definir la multiplicación de enteros no negativos de forma recursiva para convertirla en una serie de adiciones:

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

Si ese poco acerca de la transformación de la multiplicación en una serie de adiciones no tiene sentido, intente expandir algunos ejemplos simples para ver cómo funciona.

La clasificación de fusión tiene una encantadora definición recursiva:

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

Las definiciones recursivas están por todas partes si sabes qué buscar. Observe cómo todas estas definiciones tienen casos básicos muy simples, por ejemplo , gcd (m, 0) = m. Los casos recursivos reducen el problema para llegar a las respuestas fáciles.

¡Con esta comprensión, ahora puede apreciar los otros algoritmos en el artículo de Wikipedia sobre recursión !

Cualquier algoritmo exhibe recursión estructural en un tipo de datos si básicamente consiste en una instrucción switch con un caso para cada caso del tipo de datos.

por ejemplo, cuando estás 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

Esta es realmente la forma más obvia de escribir cualquier algoritmo que funcione en una estructura de datos.

Ahora, cuando miras los enteros (bueno, los números naturales) como se definen usando los axiomas de Peano

integer = 0 | succ(integer)

ves que un algoritmo recursivo estructural en 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 conocida es el ejemplo más trivial de esta forma.

En el sentido más básico de la informática, la recursión es una función que se llama a sí misma. Digamos que tienes una estructura de lista vinculada:

struct Node { Node* next; };

Y desea saber cuánto tiempo dura una lista enlazada, puede hacer esto con recursión:

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

(Por supuesto, esto también podría hacerse con un bucle for, pero es útil como ilustración del concepto)

En un lenguaje sencillo, la recursión significa repetir algo una y otra vez.

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

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

public int fact(int n) { if (n==0) return 1; else return n*fact(n-1) }

En un lenguaje sencillo: Supongamos que puedes hacer 3 cosas:

Toma una manzana
Anote las marcas de conteo
Contar marcas de conteo

Tienes muchas manzanas frente a ti en una mesa y quieres 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 recursión.

Espero que esta sea la respuesta "en inglés simple" que estás buscando!

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

Yo uso Java para trabajar, y Java no admite funciones anidadas. Como tal, si quiero hacer una recursión, podría tener que definir una función externa (que existe solo porque mi código choca contra la regla burocrática de Java), o podría tener que refactorizar el código por completo (lo que realmente odio hacer).

Por lo tanto, a menudo evito la recursión y, en cambio, uso la operación de pila, porque la recursión en sí misma es esencialmente una operación de pila.

Hay una serie de buenas explicaciones de recursion en este hilo, esta respuesta trata sobre por qué no debería usarlo en la mayoría de los idiomas. * En la mayoría de las implementaciones de lenguaje imperativo principales (es decir, cada implementación principal de C, C ++, Basic, Python). , Ruby, Java y C #) la iteration es muy preferible a la recursión.

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

el espacio está tallado en la pila para los argumentos de la función y las variables locales
Los argumentos de la función se copian en este nuevo espacio.
El control salta a la función.
el código de la función se ejecuta
El resultado de la función se copia en un valor de retorno.
La pila se rebobina a su posición anterior.
El control salta hacia donde se llamaba la función.

Realizar todos estos pasos lleva tiempo, generalmente un poco más de lo que se necesita para recorrer un bucle. Sin embargo, el problema real está en el paso # 1. Cuando se inician muchos programas, asignan una sola porción de memoria para su pila, y cuando se quedan sin esa memoria (a menudo, pero no siempre debido a la recursión), el programa se bloquea debido a un desbordamiento de pila .

Entonces, en estos idiomas, la recursión es más lenta y te hace vulnerable a los choques. Todavía hay algunos argumentos para usarlo sin embargo. En general, el código escrito de forma recursiva es más corto y un poco más elegante, una vez que sabes cómo leerlo.

Existe una técnica que los implementadores de lenguaje pueden utilizar 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 de función, entonces no es necesario que agregue un nuevo nivel a la pila, puede reutilizar el actual para la función a la que se llama. Lamentablemente, pocas implementaciones imperativas de lenguaje tienen una optimización de llamadas de cola incorporada.

* Me encanta la recursión. Mi lenguaje estático favorito no usa bucles en absoluto, la recursión 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 a ella.

** Por cierto, Mario, el nombre típico de su función ArrangeString es "join", y me sorprendería que su idioma de elección aún no tenga una implementación.

Inglés simple ejemplo de recursión.

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.

La recursión como se aplica a la programación es básicamente llamar a una función desde dentro de su propia definición (dentro de sí misma), con diferentes parámetros para realizar una tarea.

La recursión es el proceso en el que un método se llama a sí mismo para poder realizar una determinada tarea. Reduce la redundancia de código. La mayoría de las funciones o métodos recursivos deben tener una condición para interrumpir la llamada recusiva, es decir, evitar que se llame a sí misma si se cumple una condición; esto evita la creación de un bucle infinito. No todas las funciones son adecuadas para ser usadas recursivamente.

La recursión es resolver un problema con una función que se llama a sí misma. Un buen ejemplo de esto es una función factorial. Factorial es un problema matemático en el que el factorial de 5, por ejemplo, es 5 * 4 * 3 * 2 * 1. Esta función resuelve esto en C # para enteros positivos (no probado, puede haber un error).

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

La recursión es un método para resolver problemas basados en la mentalidad de dividir y vencer. La idea básica es que tomas el problema original y lo divides en instancias más pequeñas (más fáciles de resolver) de sí mismo, resuelves esas instancias más pequeñas (generalmente usando el mismo algoritmo de nuevo) y luego las vuelves a reunir 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 en la solución iterativa y debería tener sentido para cualquier persona familiarizada con C #.

La solución recursiva se encuentra al reconocer que el enésimo factorial es n * Fact (n-1). O para decirlo de otra manera, si sabe qué es un número factorial en particular, puede 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 un caso base (o, a veces, cláusula de protección) y es lo que evita que el algoritmo se ejecute para siempre. Simplemente devuelve el valor 1 siempre que se llame 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 en 1) y luego multiplicamos el resultado con nuestra copia de n.

Cuando se encuentra por primera vez, esto puede ser un poco confuso, por lo que es instructivo examinar cómo funciona cuando se ejecuta. Imagina que llamamos FactRec (5). Entramos en 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 al método con el parámetro 4, nuevamente no estamos detenidos por la cláusula de guarda 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 darle una idea de cómo se llegó 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 algrebérica simple para resolver que se compara directamente con la definición de factoriales en primer lugar.

Es instructivo tener en cuenta que cada llamada al método da como resultado que se desencadene 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, entonces el método se ejecutará para siempre.

La recursión es una expresión que se hace referencia directa o indirectamente a sí misma.

Considere las siglas recursivas como un ejemplo simple:

GNU significa GNU''s No Unix
PHP significa PHP: preprocesador de hipertexto
YAML significa YAML Ain''t Markup Language
VINO significa vino no es un emulador
VISA significa Visa International Service Association

Más ejemplos en Wikipedia

La recursión funciona mejor con lo que me gusta llamar "problemas fractales", donde se trata de una cosa grande que está hecha de versiones más pequeñas de esa cosa grande, cada una de las cuales es una versión aún más pequeña de la cosa grande, 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 recursión por varias razones:

La mayoría de las personas (incluido yo mismo) cortan sus mentes de programación en programación de procedimiento o orientada a objetos en lugar de programación funcional. Para esas personas, el enfoque iterativo (normalmente utilizando bucles) se siente más natural.
Aquellos de nosotros que nos cortamos los dientes de programación en la programación de procedimientos o orientada a objetos se nos ha dicho a menudo que eviten la recursión porque es propenso a errores.
A menudo se nos dice que la recursión es lenta. Llamar y regresar de una rutina repetidamente implica un montón de empujar y estallar en la pila, que es más lento que el bucle. Creo que algunos idiomas manejan esto mejor que otros, y esos idiomas probablemente no son aquellos en los que el paradigma dominante es de procedimiento o está orientado a objetos.
Para al menos un par de lenguajes de programación que he usado, recuerdo haber escuchado recomendaciones de no usar la recursión si llega más allá de cierta profundidad porque su pila no es tan profunda.

La recursión se refiere a un método que resuelve un problema al resolver una versión más pequeña del problema y luego usar ese resultado más algún otro cálculo para formular la respuesta al problema original. Muchas veces, en el proceso de resolver la versión más pequeña, el método resolverá una versión aún más pequeña del problema, y así sucesivamente, hasta que llegue a un "caso base" que es fácil de resolver.

Por ejemplo, para calcular un factorial para el número X , uno puede representarlo como X times the factorial of X-1 . Por lo tanto, el método "recurre" para encontrar el factorial de X-1 , y luego multiplica todo lo que obtuvo por X para dar una respuesta final. Por supuesto, para encontrar el factorial de X-1 , primero se calculará el factorial de X-2 , y así sucesivamente. ¡El caso base sería cuando X es 0 o 1, en cuyo caso se sabe que debe devolver 1 desde 0! = 1! = 1 0! = 1! = 1 0! = 1! = 1 .

Me gusta esta definición:
En la recursión, una rutina resuelve una pequeña parte del problema en sí, divide el problema en partes más pequeñas y luego se llama a sí mismo para resolver cada una de las partes más pequeñas.

También me gusta la discusión de Steve McConnells sobre la recursión en Code Complete, donde critica los ejemplos utilizados en los libros de Informática sobre Recursión.

No use la recursión para los factoriales o los números de Fibonacci

Un problema con los libros de texto de informática es que presentan ejemplos tontos de recursión. Los ejemplos típicos son el cálculo de un factorial o el cálculo de una secuencia de Fibonacci. La recursión es una herramienta poderosa, y es realmente tonto usarla en cualquiera de esos casos. Si un programador que trabajara para mí usara la recursión para calcular un factorial, contrataría a alguien más.

Pensé que este era un punto muy interesante para plantear y podría ser una razón por la que la recursión a menudo se malinterpreta.

EDIT: Esto no fue una excavación en la respuesta de Dav - no había visto esa respuesta cuando publiqué este

Para responder a un problema resuelto: no hacer nada, ya está hecho.
Para prestar atención a un problema abierto: realice el siguiente paso y, a continuación, repita en el resto.

Quieres usarlo en cualquier momento que tengas una estructura de árbol. Es muy útil en la lectura de XML.

Un ejemplo: una definición recursiva de una escalera es: Una escalera consiste en: - un solo escalón y una escalera (recursión) - o solo un solo paso (terminación)

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 atravesar una estructura de árbol. Por ejemplo, si tengo un TreeView con casillas de verificación (piense en la instalación de un nuevo programa, "elija las características para instalar" en la página), es posible que desee un botón "revisar 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); } }

Así que puedes ver que checkRecursively primero verifica el nodo por el que se pasa, luego se llama a sí mismo para cada uno de los hijos de ese nodo.

Necesitas tener un poco de cuidado con la recursión. Si te metes en un bucle recursivo infinito, obtendrás una excepción de desbordamiento de pila :)

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

Creo que debido a que es una técnica interesante, algunos programadores quizás terminen usándola más a menudo de lo que deberían, sin una justificación real. Esto ha dado un mal nombre a la recursión en algunos círculos.

Una función recursiva es una función que contiene una llamada a sí misma. Una estructura recursiva es una estructura que contiene una instancia de sí misma. Puedes combinar los dos como una clase recursiva. La parte clave de un elemento recursivo es que contiene una instancia / llamada de sí mismo.

Considera dos espejos uno frente al otro. Hemos visto el efecto infinito que hacen. Cada reflejo es una instancia de un espejo, que está contenido dentro de otra instancia de un espejo, etc. El espejo que contiene un reflejo de sí mismo es la recursión.

Un árbol de búsqueda binario es un buen ejemplo de programación de recursión. La estructura es recursiva con cada nodo que contiene 2 instancias de un nodo. Las funciones para trabajar en un árbol de búsqueda binario también son recursivas.

hey, disculpe si mi opinión está de acuerdo con alguien, solo estoy tratando de explicar la recursión en un lenguaje sencillo.

Supongamos que tienes tres gerentes: Jack, John y Morgan. Jack administra 2 programadores, John - 3 y Morgan - 5. le dará a cada gerente 300 $ y querrá saber cuánto costaría. La respuesta es obvia, pero ¿y si 2 de los empleados de Morgan-s también son gerentes?

AQUÍ viene la recursión. empiezas desde la parte superior de la jerarquía. El costo veraniego es de 0 $. empiezas con Jack, luego verifica si él tiene algún gerente como empleado. Si encuentra alguno de ellos, verifique si tienen gerentes como empleados, etc. Agregue 300 $ al costo de verano cada vez que encuentre un gerente. Cuando hayas terminado con Jack, ve con John, sus empleados y luego con Morgan.

Nunca sabrá cuántos ciclos pasará antes de recibir una respuesta, aunque sabe cuántos gerentes tiene y cuánto presupuesto puede gastar.

La recursión es un árbol, con ramas y hojas, llamados padres e hijos respectivamente. Cuando usas un algoritmo de recursión, más o menos conscientemente estás construyendo un árbol a partir de los datos.

"Si tengo un martillo, haz que todo parezca un clavo".

La recursión es una estrategia de resolución de problemas para problemas enormes , donde cada paso simplemente "convierte 2 cosas pequeñas en una cosa más grande", cada vez con el mismo martillo.

Ejemplo

Supongamos que su escritorio está cubierto con un desorden desorganizado de 1024 papeles. ¿Cómo se hace una pila de papeles ordenada y limpia del desorden, usando la recursión?

Dividir: separe todas las hojas, de modo que tenga solo una hoja en cada "pila".
Conquistar:
1. Ir alrededor, poniendo cada hoja encima de otra hoja. Ahora tienes pilas de 2.
2. Ir alrededor, poniendo cada pila de 2 encima de otra pila de 2. Ahora tienes pilas de 4.
3. Ir alrededor, poniendo cada 4 pilas encima de otras 4 pilas. Ahora tienes pilas de 8.
4. ... incesantemente ...
5. ¡Ahora tienes una pila enorme de 1024 hojas!

Tenga en cuenta que esto es bastante intuitivo, además de contar todo (lo que no es estrictamente necesario). Es posible que no vayas hasta las pilas de 1 hoja, en realidad, pero podrías y aún funcionaría. La parte importante es el martillo: con tus brazos, siempre puedes poner una pila encima de la otra para hacer una pila más grande, y no importa (dentro de lo razonable) qué tan grande es cada pila.

Una declaración recursiva es aquella en la que define el proceso de qué hacer a continuación como una combinación de las entradas y lo que ya ha hecho.

Por ejemplo, toma 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).

Así que en general:

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

Por supuesto, lo complicado de la recursión es que si desea definir las cosas en términos de lo que ya ha hecho, es necesario que haya un lugar para comenzar.

En este ejemplo, solo hacemos un caso especial definiendo factorial (1) = 1.

Ahora lo vemos de 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

Como definimos factorial (1) = 1, alcanzamos el "fondo".

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

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

2) Una parte base, que asegura que el proceso no se repita para siempre, dándole un lugar para comenzar (es decir, factorial(1) = 1 )

Puede ser un poco confuso moverte la cabeza al principio, pero solo observa un montón de ejemplos y todos deberían unirse. Si desea una comprensión mucho más profunda del concepto, estudie la inducción matemática. Además, tenga en cuenta que algunos idiomas se optimizan para llamadas recursivas, mientras que otros no lo hacen. Es bastante fácil hacer funciones recursivas increíblemente lentas si no tienes cuidado, pero también hay técnicas para hacerlas más eficaces en la mayoría de los casos.

Espero que esto ayude...