Recursividad con vectores en Java

[hystd]

Sólo quería hacer un pequeño inciso con respecto a lo que comenta Marchi:

Siguiendo tu idea podrias cambiar bubble sort por quick sort o merge sort, que son bastante mas eficientes.

Si los vectores a ordenar son de tamaños pequeños (no más de unos 20 ó 30 elementos) es mejor utilizar un algoritmo de ordenación directo (inserción, selección, burbuja, etc...), ya que éstos, a pesar de tener cotas O(n^2), responden mejor que los rápidos (QuickSort, MergeSort, HeapSort, etc...), con costes de O(n*log n), y O(n^2) para el caso de QuickSort, en caso de una mala elección del pivote o simplemente el caso de que el vector ya está ordenado (caso peor).

La razón por la que los directos son mejores en casos de vectores pequeños, es debida normalmente a las constantes multiplicativas. Hasta cierto umbral, la función T1(n)=k1*n^2 es más pequeña que T2(n)=k2*n*log n. A partir de dicho valor, las funciones se cortan y ya es más eficiente utilizar un algoritmo de ordenación rápido que uno directo. Empíricamente se puede observar que los algoritmos recursivos suelen ser más costosos que los iterativos puesto que en cada llamada hay que salvar contextos, ejecutar y recuperar contexto (continuos CALL y RETN), y en los iterativos siemplemente es realizar un bucle (o varios) sumando o restando valores en registros del procesador.

Un saludo.

[Marchi]

Muy cierto lo que dices hystd, con tamaños relativamente pequeños de arreglos, no se puede apreciar la eficiencia de estos algoritmos con respecto a los mas simples insertion, selection o bubble entre otros. Por otro lado tienen una implementacion recursiva extremadamente simple.

Y tambien tenes razon con respecto al mayor costo de los algoritmos recursivos en comparacion con sus contrapartes iterativas.
Lo interesante es que programando con un poquito de cuidado hay un gran numero de problemas que se pueden resolver con tail recursions que muchos de los compiladores modernos son capaces de detectar y compilar optimizando como si de un algoritmo iterativo se tratase.
De hecho hay grupo mas amplio de problemas que son resolubles mediante linear recursions transformables en tail recursive.


Notese que el algoritmo que puse es tail recursive, , por lo que (con el compilador adecuado) no nos cargaria con el excesivo uso de pila, llamadas a funciones y todas las otras cosas que vienen de regalo.


Saludos

[hystd]

Ok, si un compilador es capaz de transformar la recursión en iteración, para tamaños pequeños el resultado es eficiente, pero ¿y si lo hace cuando se trata de vectores grandes?

Normalmente un compilador no debe tocar el tema de la recursión si no está muy seguro de que lo que está haciendo es realmente más eficiente que el propio código escrito. Es decir, si es capaz de detectar hasta qué umbral es mejor iteración que recursión.

Teóricamente, si no tenemos en cuenta el tamaño de los vectores, un "n" desconocido y que puede ser todo lo grande que se quiera, la función T1(n)=n*log n es más pequeña SIEMPRE que T2(n)=n^2. Es decir, ignoramos las constantes multiplicativas debidas a los problemas que hemos comentado. Puesto que como no sabemos cómo de grandes son los vectores del problema, podemos usar siempre algoritmos recursivos, tal y como comentabas antes y así nos lavamos las manos por si se diera el caso de vectores grandes. Pero lo que yo me refiero es que si sabemos que los vectores son pequeños, entonces aplicamos métodos directos y listo.

Un ejemplo claro de todo esto es el MergeSort, que cuando alcanza un umbral, utiliza métodos directos.

Un saludo.

[Marchi]

Es que precisamente yo no cuestiono lo que decias en el post #21, el compilador solo cambia (cuando lo hace, valga la redundancia) la recursion por una iteracion, no es que cambia el algoritmo. Por lo tanto se va a comportar de la misma manera pero disminuyendo algunas constantes, las cuales se deben al uso de la pila y todas las cosas que habias mensionado.
En consecuencia, dado un algoritmo A tail recursive, compilado con un compilador que permita esta optimizacion de la que estamos hablando, tendra el mismo comportamiento asintotico que el mismo algoritmo A compilado sin optimizar, pero con una constante menor. La optimizacion es tanto para valores chicos como grandes de n (el tamaño de la entrada).

Para que quede mas claro voy a poner un ejemplo:

Supongamos que tengo una implementacion no tail recursive de quicksort, me esfuerzo y la hago tail recursive. Ahora el compilador la optimiza y termina generando un binario como si hubiera programado quicksort de forma iterativa.
A pesar de que ahora tengo un binario de un "algoritmo iterativo", el comportamiento asintotico es el mismo y para valores pequeños de entrada va seguir siendo mejor usar algoritmos insertion o selection, la diferencia es que probablemente el tamaño de entrada en el que se produce el "corte" sea mas pequeño.


Bueno, creo es todo por ahora.


Saludos

[hystd]

Ok, no te había entendido bien...

Siempre es posible transformar una recursión en iteración y viceversa (está demostrado matemáticamente que si es posible).

En cuanto al problema, vuelvo a decir que hay que ver cómo son los vectores de entrada. Si son pequeños, utilizar algoritmos directos es la mejor solución (así evitamos arriesgarnos a que el compilador sea o no capaz de reducir constantes multiplicativas). Si son grandes, utilizar algoritmos de ordenación rápidos.

Si no lo sabemos, ante la duda, emplear estos últimos, con la pega que no será tan eficiente en caso de que vengan pequeños.


Un saludo.