10
Me preguntaron en una entrevista, la forma eficiente de resolver un problema al buscar el pallindrome.Complejidad del espacio del algoritmo recursivo
Ahora puedo hacer dos cosas:
- a partir de i = 0 hasta i = n/2 y la comparación de ith y n-i-ésimo carácter a ser iguales.
- Puedo usar la recursividad para verificar si la primera y la última son iguales y el resto de la cadena es un pallindrome.
El segundo es recursivo. Mi pregunta es: ¿cuál es la diferencia en la complejidad del espacio de las versiones recursiva y no recursiva de un algoritmo?
Para grandes conjuntos de datos, incluso con recursividad de cola, dará lugar a un error de StackOverflow. ¿No? – Sudhakar
@Sudhakar Eso es exactamente lo que previene la optimización de recurrencia de cola :) –
Es este programa un ejemplo válido de Recursividad de cola. Esto produce stackoverflow. Por favor corrígeme si iam mal.
public class TailTest { \t public static void main(String[] args) { \t \t System.out.println(TailTest.iterate(100000)); \t } \t \t public static long iterate(int n){ \t \t if(n==1) return 1; \t \t \t \t return iterate(n-1); \t } }– Sudhakar