Invertir una cadena: Recursión vs iteración en javascript

Hace un mes, he sido entrevistado por algunos miembros de PTO de Google. Una de las preguntas era: Invertir una cadena de forma recursiva en js y explicar el tiempo de ejecución por la notación O grandeInvertir una cadena: Recursión vs iteración en javascript

este fue mi solución:

function invert(s){ 
    return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s; 
}

Bastante simple, creo.

Y, sobre la notación big-o, respondí rápidamente O (n) ya que el tiempo de ejecución depende linealmente de la entrada. - Silencio - y luego, me preguntó, ¿cuáles son las diferencias en términos de tiempo de ejecución si lo implementas por iteración?

Respondí que a veces el compilador "traduce" la recursión en iteración (algunas memorias del curso del lenguaje de programación) por lo que no hay diferencias sobre la iteración y la recursión en este caso. Por cierto, dado que no tenía comentarios sobre esta pregunta en particular, y el entrevistador no respondió "ok" o "nope", me gustaría saber si usted está de acuerdo conmigo o si puede explicarme si podría haber diferencias sobre el 2 tipo de implementaciones.

Muchas gracias y Saludos cordiales.

Fuente

2011-01-17 stecb

No estoy seguro, pero podría haber una sobrecarga de generación de pila de llamadas en el recursividad, que no habría una en un bucle. –

Por cierto, habría almacenado la longitud en lugar de acceder a ella 3 veces, pero tal vez no había necesidad de optimización ... (lo siento, siempre optimizo prematuramente, es una de mis muchas fallas) –

@Martin: generación de pila de llamadas debería ser una * muy * pequeña sobrecarga. En cualquier caso, el código aquí recursá n veces, tiene la misma complejidad computacional que un ciclo que itera n veces. – Juliet

Su solución se ve O (n ²) para mí. La llamada a substring es muy probable O (n) - una implementación típica asignará espacio para una nueva cadena y luego copiará la subcadena. [Pero vea los comentarios.] La concatenación de cadenas + también será probablemente O (n). Incluso puede ser el caso que length sea O (n) pero creo que esto es bastante improbable.

Has sacado a colación la idea de que un compilador puede transformar la recursividad en iteración. Esto es cierto, pero rara vez se implementa fuera de los lenguajes funcionales y Scheme; y típicamente la única transformación que se aplica es eliminación de recurrencia de cola. En su código, la recursión no está en posición de cola: después de la llamada recursiva a invert, todavía debe calcular el +. Así que la eliminación de la recursividad de la cola no se aplica a su código.

Eso significa que una versión iterativa de invert tendría que implementarse de una manera diferente. Puede tener la misma o diferente complejidad, no podemos decir hasta que lo hayamos visto.

Fuente

2011-01-17 21:51:03

¿De verdad? No sé muy bien javascript, pero en la mayoría de los idiomas que conozco, la subcadena es O (1), que comparte el almacenamiento de la cadena original (ya sea porque las cadenas son inmutables o las subcadenas se implementan usando copy-on-write). – sepp2k

La pregunta no especificaba qué implementación de JavaScript se estaba utilizando, de ahí mis advertencias. (Una vez implementé JavaScript y mi 'substring' era O (n), ¡así que es cierto para al menos una implementación de JS!) Pero incluso si tienes razón sobre' substring', parece probable que '' 'sea O (norte). –

@ sepp2k: El problema con la subcadena O (1) es que realmente arruina la recolección de basura. Si asigno una cadena de varios megabytes, saco 5 caracteres del medio y luego dejo que la cadena original salga del alcance, aún no es elegible para la recopilación porque la pequeña subcadena todavía está flotando. –

En una nota lateral, para usar recursividad de cola que permite al compilador implementar su recursión como un bucle, no puede tener el estado restante en la pila. Para evitar esto, puede pasar el "estado" como un parámetro adicional a su función:

function invert(sofar, s) 
{ 
    return (s.length > 0) ? invert(s.charAt(s.length-1)+sofar, s.substring(0,s.length-1)) : sofar; 
}

Fuente

2011-01-17 22:11:15 BrokenGlass

No creo que la mayoría de los motores de JavaScript (si los hay) realizan Tail Call Optimization – jimr

Eso es cierto, solo lo mencioné desde el OP mencionó las posibilidades de optimización en su pregunta – BrokenGlass

Tiene razón @BrokenGlass. El ejemplo debería optimizar todo lo 'optimizable': D .. Creo que me preguntó acerca de este tipo de cosas solo para saber si podía hacer algo acerca de la opción ... por cierto, en este caso, ¿cree que la recursión no está "convertida"? "en la iteración? – stecb

Invertir una cadena: Recursión vs iteración en javascript

Respuesta

Cuestiones relacionadas