¿Es la recursividad una característica en sí misma?

... o es solo una practica?

Pregunto esto debido a una discusión con mi profesor: perdí el crédito por llamar a una función de forma recursiva sobre la base de que no cubrimos la recursividad en clase, y mi argumento es que la aprendimos implícitamente mediante el aprendizaje returny los 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 " acontinúa para siempre" (en el programa real se usa correctamente para avisar al usuario nuevamente cuando se le proporciona una entrada no válida), ¿hay alguna diferencia fundamental entre ay b? Para un compilador no optimizado, ¿cómo se manejan de manera diferente?

En última instancia, se reduce a si al aprender a return a()partir de bque nosotros también aprendimos para ello a return a()partir a. ¿Hicimos nosotros?

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

Al leer entre líneas, una posibilidad es que al usar la recursividad, evitó usar una característica que se suponía que era un resultado de aprendizaje para su curso. Por ejemplo, tal vez no usó iteración en absoluto, o tal vez solo usó forbucles en lugar de usar ambos fory while. Es común que una tarea tenga como objetivo probar su capacidad para hacer ciertas cosas, y si evita hacerlas, su profesor simplemente no puede otorgarle las calificaciones reservadas para esa función. Sin embargo, si esa fue realmente la causa de sus calificaciones perdidas, el profesor debe tomar esto como una experiencia de aprendizaje propia, si demostrar ciertos 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 de que la iteración es una mejor opción que la recursividad aquí. Hay un par de razones, y aunque otras personas las han mencionado hasta cierto punto, no estoy seguro de que hayan explicado completamente la idea que hay detrás de ellas.

Desbordamientos de pila

El más obvio es que corre el riesgo de obtener un error de desbordamiento de pila. Siendo realistas, es muy 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 activar un desbordamiento de pila.

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

Esto es parte de un principio más general en el diseño de software llamado abstracción. Básicamente, cuando llame DoThing(), lo único que debería preocuparle es que la cosa esté lista. 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, porque cada bit de código tiene que preocuparse por cuánta pila puede asumir 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. El ideal al que debería aspirar el código es ser un documento legible por humanos, donde cada línea describe simplemente lo que está haciendo. Adopte 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 se podrían describir los dos enfoques en inglés? Creo que sería algo como:

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

versus

Solicitaré una entrada, luego, si la entrada es válida, la devolveré; de lo contrario, obtengo la entrada y devuelvo el resultado de eso.

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

De forma aislada, ambos son puntos pequeños. Es muy poco probable que esto conduzca realmente a un desbordamiento de la pila, y la mejora en la legibilidad es menor. Pero cualquier programa va a ser una colección de muchas de estas pequeñas decisiones, por lo que incluso si de forma aislada no importan mucho, es importante aprender los principios detrás de hacerlas bien.

Para responder a la pregunta literal, más que a la metapregunta: la recursividad es una característica, en el sentido de que no todos los compiladores y / o lenguajes lo permiten necesariamente. 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 de 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 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

Con suerte, el problema cuando intentas llamar a() recursiva en un compilador de este tipo sea obvio; el compilador ya no sabe cómo regresar de la llamada externa, porque se ha sobrescrito la dirección de retorno.

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

Mirando hacia el futuro, puedo imaginar escenarios especializados, quizás sistemas muy paralelos, donde no tener que proporcionar una pila para cada hilo podría ser ventajoso y donde, por lo tanto, la recursividad solo se permite si el compilador puede refactorizarlo en un bucle. (Por supuesto, los compiladores primitivos que analizo anteriormente no eran capaces de tareas complicadas como refactorizar código).

El profesor quiere saber si has estudiado o no. Aparentemente no resolviste el problema de la manera que él te enseñó ( la buena manera ; iteración), y por lo tanto, considera que no lo hiciste. Estoy a favor de las soluciones creativas, pero en este caso tengo que estar de acuerdo con su maestro por una razón diferente:
si el usuario proporciona una entrada no válida demasiadas veces (es decir, manteniendo presionada la tecla Intro), tendrá una excepción de desbordamiento de pila y su la 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 maestro debería haberte dado.

Deducir puntos porque "no cubrimos la recursividad en clase" es horrible. Si aprendió cómo llamar a la función A que llama a la función B que llama a la función C que vuelve a B que vuelve a A que vuelve 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 las versiones antiguas de FORTRAN, por ejemplo), no hay ninguna razón por la que A, B y C no puedan ser todos la misma función.

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

Hay muchos puntos de vista para 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 tu profesor realmente te quitó las notas por usar una "función" que aún no había enseñado, estaba mal, pero como dije, hay otros puntos de vista a considerar aquí que realmente 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 entrada en caso de falla de entrada no es una buena práctica, ya que cada llamada de funciones recursivas se envía a la pila. Dado que esta recursividad es impulsada por la entrada del usuario, es posible tener una función recursiva infinita y, por lo tanto, dar como resultado un StackOverflow.

No hay diferencia entre estos 2 ejemplos que mencionó en su pregunta en el sentido de lo que hacen (pero difieren en otras formas): en ambos casos, una dirección de retorno y toda la información del método se cargan en la pila. En un caso de recursividad, 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 ve en el código en sí, sino en el código creado por el compilador). En Java, C y Python, la recursividad es bastante cara 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 dedujo puntos ya que la recursividad se considera un tema en sí mismo y es poco probable que alguien sin experiencia en programación piense en la recursividad. (Por supuesto, no significa que no lo harán, pero es poco probable).

En mi humilde opinión, creo que el profesor tiene razón al deducirle los puntos. Fácilmente podría haber llevado la parte de validación a 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 hizo realmente puede resolverse de esa manera, entonces lo que hizo fue una mala práctica y debe evitarse.

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

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

La principal desventaja de la recursividad es que los algoritmos recursivos pueden causar desbordamientos de pila, ya que cada nivel de recursividad requiere que se agregue un marco de pila adicional a la pila.

Para el código de producción, donde el escalado puede resultar en muchos más niveles de recursividad en producción que en las pruebas unitarias del programador, la desventaja generalmente supera a la ventaja, y el código recursivo a menudo se evita cuando es práctico.

Con respecto a la pregunta específica, si la recursividad es una característica, me inclino a decir que sí, pero después de reinterpretar la pregunta. Hay opciones de diseño comunes de lenguajes y compiladores que hacen posible la recursividad, y existen lenguajes completos de Turing que no permiten la recursividad 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 recursividad bajo supuestos mínimos; vea los bucles de escritura 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 utilizan enlaces tardíos o que definen declaraciones hacia adelante hacen posible la recursividad. Por ejemplo, si bien Python permite el siguiente código, esa es una elección de diseño (enlace tardío), no un requisito para un Turing-complete sistema . Las funciones recursivas mutuas a menudo dependen del soporte para declaraciones hacia adelante.

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

• Los lenguajes tipados estáticamente que permiten tipos definidos de forma recursiva contribuyen a habilitar la recursividad. Vea esta implementación del Y Combinator en Go . Sin tipos definidos de forma recursiva, aún sería posible usar la recursividad en Go, pero creo que el combinador Y específicamente sería imposible.

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

Porque cada llamada a funciones recursivas se envía a la pila. Dado que esta recursividad es impulsada por la entrada del usuario, es posible tener una función recursiva infinita y, por lo tanto, dar como resultado un StackOverflow :-p

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

La recursividad es un concepto de programación , una característica (como la iteración) y una práctica . Como puede ver en el enlace, hay un gran dominio de investigación dedicado al tema. Quizás no necesitemos profundizar tanto en el tema para comprender estos puntos.

La recursividad como 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 es el caso: podría escribir el cuerpo de ese método a, pero no podría incluir una llamada adentro de él. La única solución sería utilizar la 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 aquellas que no lo hacen. En realidad, todo un grupo de lenguajes hacen esa distinción (ver Lisp y familias ML , por ejemplo). Curiosamente, Perl incluso permite funciones anónimas (llamadaslambdas ) para llamarse a sí mismos de forma recursiva (de nuevo, con una sintaxis dedicada).

sin recursividad?

Para los lenguajes que ni siquiera admiten la posibilidad de recursividad, a menudo hay otra solución, en la forma del combinador de punto fijo , pero aún requiere que el lenguaje admita funciones como los llamados objetos de primera clase (es decir, objetos que pueden ser manipulado dentro del propio lenguaje).

La recursividad como práctica

Tener esa función disponible en un idioma no significa necesariamente que sea idiomática. En Java 8, se han incluido expresiones lambda, por lo que podría resultar más fácil adoptar un enfoque funcional de programación. Sin embargo, existen consideraciones prácticas:

• la sintaxis todavía no es muy amigable con la recursividad
• Es posible que los compiladores no puedan 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 sean conscientes de sí mismos de forma predeterminada y, por lo tanto, admiten la recursividad, por lo que este no es realmente un problema práctico, pero sigue siendo teórico, y supongo que su maestro 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.