En algunos casos, las funciones recursivas pueden ser mucho peores que sus contrapartes iterativas, especialmente en lenguajes imperativos como C / C ++ / Java, que no tienen optimización de llamadas de cola.
Sigue una descripción simplificada de Tail-Call Optimization y su aplicación para reducir la sobrecarga de recursividad.
La recursión implica la sobrecarga: asignación de marco de pila, desasignación y otras llamadas de función, pero si la declaración recursiva es la última declaración de una función, en algunos casos es posible usar el marco de pila del llamador y reemplazar la llamada de función con un goto o equivalente (por ejemplo, un bucle while con algunas variables que mantienen el estado fuera de su alcance), eliminando así la sobrecarga de la llamada de función, acelerando enormemente la recursión y, por último, lo más importante, evitando también los infames errores de desbordamiento de pila. recursión profunda o infinita, en efecto convirtiéndolas en un bucle.
- ¿Qué es el diagrama de flujo?
- ¿Se puede implementar un mapa usando Tree? ¿Se puede implementar un mapa usando List? Esto es específico de Java, pero me gustaría conocer el enfoque general.
- Cómo imprimir una cadena usando un puntero
- ¿Cómo es codicioso el algoritmo de Kruskal?
- ¿Cuál es el número de elementos comunes en dos conjuntos de permutación?
Los lenguajes funcionales como Lisp, Haskell, Scheme, etc. tienen que hacer esta optimización de cola de manera agresiva, ya que carecen de construcciones de iteración como while y for , y la recursión es la única forma de hacer iteraciones en estos lenguajes.
Sin embargo, los lenguajes comunes de la industria como C / C ++ / Java son imprescindibles, y en su mayoría (¿totalmente?) Carecen de la optimización de las llamadas de cola para las funciones recursivas (al menos de forma predeterminada (sin indicadores de compilación para C / C ++)). Así que bienvenido: StackOverflowError , ejecución lenta y, por último, pero no menos importante, depuración complicada.
Ahora no me pregunte por qué su función de ordenación rápida en Java arroja el Error anterior al pasar una matriz de millones de Object .
