java - recursivos - ¿Alguna vez no usarás la recursión?

recursividad en java ventajas y desventajas

Question

Tengo un problema para un laboratorio de la universidad;

Escriba un programa corto que muestre todas las cadenas posibles formadas utilizando los caracteres ''c'', ''a'', ''r'', ''b'', ''o'' y ''n'' exactamente una vez.

Parece ser una pregunta de entrevista común y bien documentada.

Así que lo he codificado con Java usando un método recursivo que no era demasiado difícil, ¿ cuándo o por qué elegirías no usar la recursión y cuál sería la forma más fácil de hacerlo?

Empecé a codificar un contador que cuenta regresivamente en la base 6, la salida haría referencia a los caracteres e imprimirá la cadena.

Gracias,

Answer 1

Como han escrito las personas de arriba, la recursión no siempre es la solución óptima (las llamadas a funciones pueden ser costosas y consumen la pila a menos que el compilador pueda optimizar la recursividad de cola). Sin embargo, es particularmente adecuado para problemas como el tuyo.

Aunque teóricamente es posible expresar cada algoritmo recursivo en términos de iteración (por ejemplo, simulando manualmente la pila de llamadas con una matriz), a veces la solución iterativa equivalente es menos elegante. Aquí hay una muestra:

text = ''carbon''
n = len(text)
for permutation_i in range(factorial(n)):
    free_letters = list(text)
    divisor = 1
    for character_i in range(n, 0, -1):
        letter = free_letters.pop(permutation_i//divisor%character_i)
        print(letter, end='''')
        divisor *= character_i
    print()

Answer 2

Cuando hay muchas invocaciones de recursión, tu pila puede explotar, dejándote con Error. El buen ejemplo es el cálculo de los números de Fibonacci (o problema de las torres de Hanoi) con recursión básica, no podrá calcular muchos de esos números. Que podrás utilizar mediante una versión no recurrente. Básicamente, la recursión crea una solución atractiva y esta es una virtud. Todavía puede tener una buena solución de recursión de trabajo mediante el uso de recursividad de cola

Answer 3

Simplemente use un ciclo y evitará el uso de la recursión. La recursividad se evita generalmente porque hace que el código sea menos legible y más difícil de mantener y depurar. Si tiene pocos recursos, ya que paxdiablo dijo que el espacio de pila podría ser valioso para usted, entonces debería evitar usarlo también.

Answer 4

Use recursividad cuando sus datos sean intrínsecamente jerárquicos / anidados. Use la iteración cuando sus datos sean lineales / planos.

En su caso, hay un orden natural que puede imponer sobre las combinaciones, por lo que puede tratar los datos como lineales, pero si lo ve como un árbol, termina con el enfoque recursivo.

Si la estructura de su algoritmo refleja la estructura del problema subyacente, usted termina con un código más simple que es más fácil de entender. No use la recursión solo porque su profesor de CS201 pensó que era así. ¡Guay!

Answer 5

Los algoritmos y las estructuras de datos de Niklaus Wirth tienen una sección "Cuándo no utilizar la recursión", pero la recursividad es una herramienta útil del programador. Creo que entender la recursividad es "imprescindible" para un programador.

Tienes un enfoque inteligente para el problema de permutación . Se puede resolver recursivamente (pseudocódigo):

private void PermutationsRecursive(string prefix, string s)
{
    int N = s.Length;

    if (N > 0)
        for (int i = 0; i < N; i++)
            PermutationsRecursive(prefix + s[i], s.Substring(0, i) + s.Substring(i + 1, N - i - 1));
    else
        WriteLine(prefix);
}

PermutationsRecursive("", "carbon");

Answer 6

Sí, hay muchas veces que no usaría la recursión. La recursividad no es gratuita, tiene un costo en el espacio de pila y, a menudo, puede ser un recurso mucho más limitado que otros. También hay un costo de tiempo, por pequeño que sea, para configurar y destruir los marcos de pila.

A modo de ejemplo, la función factorial muy aclamada es una en la que probablemente optaría por un enfoque iterativo donde los números eran grandes. Calculando 10000! con:

def factorial (n):
    if n = 1 return 1
    return n * factorial (n-1)

usará 10,000 marcos de pila (asumiendo que no es optimizado por el compilador en una solución iterativa, por supuesto), bastante. La solución iterativa:

def factorial (n)
    r = 1
    while n > 1:
        r = r * n
        n = n - 1
    return r

usará solo el marco de una pila y poco más.

Es cierto que las soluciones recursivas a menudo son un código más elegante, pero hay que atemperarlas con las limitaciones de su entorno.

Su ejemplo de carbon es uno en el que realmente usaría recursividad ya que:

• usa como máximo seis marcos de pila (uno por personaje en la cadena); y
• es relativamente elegante, al menos mucho más que seis bucles anidados y enormes controles de igualdad.

Por ejemplo, el siguiente código de Python es el truco:

def recur (str, pref = ""):
    # Terminating condition.

    if str == "":
        print pref
        return

    # Rotate string so all letters get a chance to be first.

    for i in range (len (str)):
        recur (str[1:], pref + str[:1])
        str = str[1:] + str[:1]

recur ("abc")

productor:

abc
acb
bca
bac
cab
cba

Por supuesto, si su cadena puede tener 10K de longitud, lo reconsideraría, ya que eso implicaría muchos más niveles de pila pero, si se mantiene lo suficientemente bajo, la recursión es una solución viable.