recursion - recursiva - recursividad de retroceso

¿Es la recursión una característica en sí misma?

Question

... ¿o es solo una práctica?

Pregunto esto por una discusión con mi profesor: perdí crédito por llamar a una función recursivamente sobre la base de que no cubrimos la recursión en clase, y mi argumento es que lo aprendimos implícitamente mediante el aprendizaje de return y métodos.

Pregunto aquí porque sospecho que alguien tiene una respuesta definitiva.

Por ejemplo, ¿cuál es la diferencia entre los dos métodos siguientes?

public static void a() {
    return a();
    }

public static void b() {
    return a();
    }

Aparte de que " a continúa para siempre" (en el programa real se usa correctamente para solicitar nuevamente a un usuario cuando se le proporciona una entrada no válida), ¿hay alguna diferencia fundamental entre a y b ? Para un compilador no optimizado, ¿cómo se manejan de manera diferente?

En última instancia, todo se reduce a si al aprender a return a() desde b , entonces también aprendimos a return a() de a . ¿Hicimos?

Answer 1

Deducir puntos porque "no cubrimos la recursión en clase" es horrible. Si aprendió a llamar a la función A que llama a la función B que llama a la función C que regresa a B que regresa a A que regresa a la persona que llama, y ​​el profesor no le dijo explícitamente que estas deben ser funciones diferentes (que sería el caso en versiones antiguas de FORTRAN, por ejemplo), no hay ninguna razón para que A, B y C no puedan ser la misma función.

Por otro lado, tendríamos que ver el código real para decidir si en su caso particular el uso de la recursividad es realmente lo correcto. No hay muchos detalles, pero suena mal.

Answer 2

El maestro quiere saber si has estudiado o no. Aparentemente no resolvió el problema de la forma en que él le enseñó ( el buen camino , la iteración) y, por lo tanto, considera que no lo hizo. Estoy a favor de soluciones creativas, pero en este caso tengo que estar de acuerdo con tu profesor por una razón diferente:
Si el usuario proporciona una entrada no válida muchas veces (es decir, manteniendo presionada la tecla enter), tendrá una excepción de desbordamiento de pila y su solución se bloqueará. Además, la solución iterativa es más eficiente y más fácil de mantener. Creo que esa es la razón por la que tu maestra debería haberte dado.

Answer 3

En cuanto a la pregunta específica, la recursividad es una característica, me inclino a decir que sí, pero después de volver a interpretar la pregunta. Hay opciones de diseño comunes de lenguajes y compiladores que hacen posible la recursión, y existen lenguajes completos de Turing que no permiten la recursión en absoluto . En otras palabras, la recursividad es una habilidad habilitada por ciertas elecciones en el diseño del lenguaje / compilador.

• El soporte de funciones de primera clase hace posible la recursión bajo suposiciones muy mínimas; vea escribir bucles en Unlambda para ver un ejemplo, o esta expresión obtusa de Python que no contiene autorreferencias, bucles o asignaciones:

  >>> map((lambda x: lambda f: x(lambda g: f(lambda v: g(g)(v))))(
  ...   lambda c: c(c))(lambda R: lambda n: 1 if n < 2 else n * R(n - 1)),
  ...   xrange(10))
  [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

• Los lenguajes / compiladores que usan enlace tardío , o que definen declaraciones directas, hacen posible la recursión. Por ejemplo, si bien Python permite el siguiente código, esa es una opción de diseño (enlace tardío), no un requisito para un sistema Turing-complete . Las funciones mutuamente recursivas a menudo dependen del soporte para declaraciones futuras.

  factorial = lambda n: 1 if n < 2 else n * factorial(n-1)

• Los lenguajes de tipo estático que permiten tipos definidos recursivamente contribuyen a habilitar la recursión. Ver esta implementación del Y Combinator en Go . Sin tipos definidos recursivamente, aún sería posible usar la recursión en Go, pero creo que el combinador Y específicamente sería imposible.

Answer 4

Hay muchos puntos de vista a considerar con respecto a la pregunta específica que hizo, pero lo que puedo decir es que, desde el punto de vista del aprendizaje de un idioma, la recursividad no es una característica en sí misma. Si su profesor realmente atracó sus marcas por usar una "característica" que aún no había enseñado, eso estaba mal, pero como he dicho, hay otros puntos de vista que considerar que hacen que el profesor tenga razón al deducir puntos.

Por lo que puedo deducir de su pregunta, usar una función recursiva para solicitar información en caso de falla en la entrada no es una buena práctica ya que cada llamada a funciones recursivas pasa a la pila. Dado que esta recursión es impulsada por la entrada del usuario, es posible tener una función recursiva infinita y, por lo tanto, resulta en un .

No hay diferencia entre estos 2 ejemplos que mencionó en su pregunta en el sentido de lo que hacen (pero difieren de otras maneras): en ambos casos, se carga una dirección de retorno y toda la información del método en la pila. En un caso de recursión, la dirección de retorno es simplemente la línea justo después de la llamada al método (por supuesto, no es exactamente lo que se ve en el código en sí, sino más bien en el código creado por el compilador). En Java, C y Python, la recursividad es bastante costosa en comparación con la iteración (en general) porque requiere la asignación de un nuevo marco de pila. Sin mencionar que puede obtener una excepción de desbordamiento de pila si la entrada no es válida demasiadas veces.

Creo que el profesor resta puntos ya que la recursividad se considera un tema propio y es poco probable que alguien sin experiencia en programación piense en la recursión. (Por supuesto que no significa que no lo harán, pero es poco probable).

En mi humilde opinión, creo que el profesor tiene razón al restarle los puntos. Podría haber tomado fácilmente la parte de validación en un método diferente y usarlo así:

public bool foo() 
{
  validInput = GetInput();
  while(!validInput)
  {
    MessageBox.Show("Wrong Input, please try again!");
    validInput = GetInput();
  }
  return hasWon(x, y, piece);
}

Si lo que hiciste puede ser resuelto de esa manera, entonces lo que hiciste fue una mala práctica y debería evitarse.

Answer 5

Para responder a la pregunta literal, en lugar de a la meta-pregunta: la recursión es una característica, en el sentido de que no todos los compiladores y / o lenguajes necesariamente lo permiten. En la práctica, se espera de todos los compiladores modernos (ordinarios), ¡y ciertamente de todos los compiladores de Java! - pero no es universalmente cierto.

Como un ejemplo artificial de por qué la recursión podría no ser compatible, considere un compilador que almacena la dirección de retorno para una función en una ubicación estática; este podría ser el caso, por ejemplo, de un compilador para un microprocesador que no tiene una pila.

Para tal compilador, cuando llamas a una función como esta

a();

se implementa como

move the address of label 1 to variable return_from_a
jump to label function_a
label 1

y la definición de a (),

function a()
{
   var1 = 5;
   return;
}

se implementa como

label function_a
move 5 to variable var1
jump to the address stored in variable return_from_a

Esperemos que el problema cuando intentes llamar a() recursivamente en un compilador así sea obvio; el compilador ya no sabe cómo regresar desde la llamada externa, porque la dirección de retorno ha sido sobrescrita.

Para el compilador que realmente utilicé (finales de los 70 o principios de los 80, creo) sin soporte para la recursión, el problema fue un poco más sutil: la dirección de retorno se almacenaría en la pila, como en los compiladores modernos, pero las variables locales no ''t. (En teoría, esto debería significar que la recursión era posible para las funciones sin variables locales no estáticas, pero no recuerdo si el compilador lo admitió explícitamente o no. Puede que haya necesitado variables locales implícitas por algún motivo).

Mirando hacia adelante, puedo imaginar escenarios especializados - sistemas fuertemente paralelos, tal vez - donde no tener que proporcionar una pila para cada hilo podría ser ventajoso, y donde, por lo tanto, la recursión solo está permitida si el compilador puede refactorizarlo en un bucle. (Por supuesto, los compiladores primitivos que analicé anteriormente no eran capaces de tareas complicadas como el código de refactorización).

Answer 6

Para responder a su pregunta específica: No, desde el punto de vista de aprender un idioma, la recursividad no es una característica. Si tu profesor realmente atracó tus notas por usar una "función" que aún no había enseñado, eso estaba mal.

Al leer entre líneas, una posibilidad es que al usar la recursión, evitaste utilizar alguna función que supuestamente era un resultado de aprendizaje para su curso. Por ejemplo, tal vez no usaste la iteración en absoluto, o tal vez solo usaste bucles for lugar de usar for y while . Es común que una tarea tenga como objetivo probar tu capacidad para hacer ciertas cosas, y si evitas hacerlas, tu profesor simplemente no puede otorgarte las calificaciones reservadas para esa función. Sin embargo, si esa fue realmente la causa de sus marcas perdidas, el profesor debe tomar esto como una experiencia de aprendizaje propia; si demostrar los resultados de aprendizaje es uno de los criterios para una tarea, eso debe explicarse claramente a los estudiantes. .

Habiendo dicho eso, estoy de acuerdo con la mayoría de los otros comentarios y respuestas en que la iteración es una mejor opción que la recursión aquí. Hay un par de razones, y aunque otras personas las han abordado hasta cierto punto, no estoy seguro de que hayan explicado completamente el pensamiento detrás de ellas.

Desbordamientos de pila

El más obvio es que te arriesgas a obtener un error de desbordamiento de pila. Siendo realistas, es poco probable que el método que escribió conduzca a uno, ya que un usuario tendría que dar una entrada incorrecta muchas veces para desencadenar un desbordamiento de la pila.

Sin embargo, una cosa a tener en cuenta es que no solo el método en sí, sino que otros métodos más altos o más bajos en la cadena de llamadas estarán en la pila. Debido a esto, casualmente devorar el espacio de pila disponible es una cosa bastante descortés para cualquier método. Nadie quiere tener que preocuparse constantemente por el espacio libre de la pila cada vez que escriba el código debido al riesgo de que otro código haya utilizado innecesariamente una gran cantidad de él.

Esto es parte de un principio más general en el diseño de software llamado abstracción. Básicamente, cuando llamas a DoThing() , todo lo que deberías preocuparte es que eso está hecho. No debería tener que preocuparse por los detalles de implementación de cómo se hace. Pero el uso codicioso de la pila rompe este principio, ya que cada bit de código tiene que preocuparse por la cantidad de pila que puede suponer con seguridad que le ha dejado el código en otra parte de la cadena de llamadas.

Legibilidad

La otra razón es la legibilidad. Lo ideal a lo que debe aspirar el código es a ser un documento legible por humanos, donde cada línea describe simplemente lo que está haciendo. Toma estos dos enfoques:

private int getInput() {
    int input;
    do {
        input = promptForInput();
    } while (!inputIsValid(input))
    return input;
}

versus

private int getInput() {
    int input = promptForInput();
    if(inputIsValid(input)) {
        return input;
    }
    return getInput();
}

Sí, ambos funcionan, y sí, ambos son bastante fáciles de entender. Pero, ¿cómo podrían describirse los dos enfoques en inglés? Creo que sería algo así como:

Pediré la entrada hasta que la entrada sea válida, y luego la devolveré

versus

Pediré la entrada, luego, si la entrada es válida, la devolveré; de lo contrario, obtendré la entrada y devolveré el resultado de eso

Quizás pueda pensar en una fraseología menos torpe para este último, pero creo que siempre encontrará que la primera va a ser una descripción más precisa, conceptualmente, de lo que en realidad está tratando de hacer. Esto no quiere decir que la recursión sea siempre menos legible. Para las situaciones en las que brilla, como el cruce de árboles, podría hacer el mismo tipo de análisis lado a lado entre la recursividad y otro enfoque, y casi seguramente encontraría que la recursividad proporciona un código que es más claramente autodescriptivo, línea por línea.

De manera aislada, ambos son puntos pequeños. Es muy poco probable que esto conduzca realmente a un desbordamiento de pila, y la ganancia en legibilidad es menor. Pero cualquier programa va a ser una colección de muchas de estas decisiones pequeñas, por lo que incluso si de manera aislada no importan demasiado, es importante aprender los principios para hacer que funcionen correctamente.

Answer 7

Por lo que puedo deducir de su pregunta, usar una función recursiva para pedir información en caso de falla de la entrada no es una buena práctica. ¿Por qué?

Debido a que cada llamada de funciones recursivas se empuja a la pila. Dado que esta recursión es impulsada por la entrada del usuario, es posible tener una función recursiva infinita y, por lo tanto, resulta en un :-p

Tener un ciclo no recursivo para hacer esto es el camino a seguir.

Answer 8

Tal vez su profesor todavía no lo haya enseñado, pero parece que está listo para aprender las ventajas y desventajas de la recursión.

La principal ventaja de la recursión es que los algoritmos recursivos suelen ser mucho más fáciles y rápidos de escribir.

La principal desventaja de la recursión es que los algoritmos recursivos pueden causar desbordamientos de pila, ya que cada nivel de recursión requiere un marco de pila adicional para agregarse a la pila.

Para el código de producción, donde la escala puede dar como resultado muchos más niveles de recursión en la producción que en las pruebas unitarias del programador, la desventaja suele ser mayor que la ventaja, y el código recursivo a menudo se evita cuando es práctico.

Answer 9

Recursion es un concepto de programación, una función (como la iteración) y una práctica . Como puede ver en el enlace, hay un gran dominio de investigación dedicado al tema. Tal vez no necesitemos profundizar en el tema para comprender estos puntos.

La recursividad como una característica

En términos simples, Java lo soporta implícitamente, porque permite que un método (que es básicamente una función especial) tenga "conocimiento" de sí mismo y de otros métodos que componen la clase a la que pertenece. Considere un lenguaje donde este no sea el caso: podría escribir el cuerpo de ese método, pero no podría incluir una llamada a a dentro de él. La única solución sería usar iteración para obtener el mismo resultado. En tal lenguaje, tendría que hacer una distinción entre funciones conscientes de su propia existencia (mediante el uso de un token de sintaxis específico), y aquellos que no lo hacen. En realidad, todo un grupo de idiomas distingue (por ejemplo, las familias Lisp y ML ). Curiosamente, Perl incluso permite funciones anónimas (llamadas lambdas ) para llamarse recursivamente (nuevamente, con una sintaxis dedicada).

sin recursividad?

Para lenguajes que ni siquiera admiten la posibilidad de recursión, a menudo existe otra solución, en forma del combinador de punto fijo , pero todavía requiere que el lenguaje admita funciones como los denominados objetos de primera clase (es decir, objetos que pueden ser manipulado dentro del lenguaje mismo).

Recursión como práctica

Tener esa característica disponible en un idioma no necesariamente significa que es idiomática. En Java 8, se han incluido las expresiones lambda, por lo que podría ser más fácil adoptar un enfoque funcional para la programación. Sin embargo, hay consideraciones prácticas:

• la sintaxis aún no es muy amigable con la recursividad
• los compiladores pueden no ser capaces de detectar esa práctica y optimizarla

La línea de fondo

Afortunadamente (o más exactamente, para facilitar su uso), Java permite que los métodos se den cuenta de sí mismos de forma predeterminada y, por lo tanto, admiten la recursión, por lo que este no es realmente un problema práctico, pero sigue siendo teórico, y supongo que su profesor quería abordarlo específicamente. Además, a la luz de la evolución reciente del lenguaje, podría convertirse en algo importante en el futuro.