Primero sin recursion, despues con recursion
Once problemas resueltos dos veces. Primero como los resolverias con bucles, que es como piensas hoy. Despues con recursion. Y al final, con numeros concretos, que fue lo que cambio.
La advertencia que casi nadie da
En cuatro de estos once problemas la recursion no mejora nada, y en uno la empeora muchisimo. Saber cuando NO usarla vale igual que saber escribirla.
Como leer esta pagina
Cada problema viene en tres o cuatro bloques numerados. Leelos en orden, sin saltarte el primero: el punto de todo esto es que compares contra algo que ya sabes hacer.
Todo el codigo esta comentado linea por linea y es Java compilable. Puedes copiarlo y pegarlo en tu IDE tal cual.
El resumen de las once
Si tuvieras que quedarte con una sola regla despues de recorrer todos estos casos, seria esta: la recursion no es una forma mas bonita de repetir. La repeticion la hace igual de bien un bucle, y casi siempre gastando menos memoria.
La recursion gana cuando el problema tiene alguna de estas tres formas:
Arboles, carpetas, JSON, el DOM de una pagina. Un nodo que contiene nodos. Ahi el algoritmo recursivo es la traduccion literal de la definicion, y la version con bucle tiene que reconstruir a mano la pila que la JVM daba gratis.
Busqueda binaria, mergesort, potencia rapida. Partir en mitades es lo que convierte n pasos en log(n) pasos. Ojo: partir a la mitad, no restarle uno. El factorial tambien es recursivo y no gana nada.
Backtracking: laberintos, N reinas, sudoku, subconjuntos. Volver atras es justo lo que hace la pila cuando un marco termina, asi que sale gratis. Con bucles hay que programar el retroceso a mano, y ahi es donde todo el mundo falla.
Cuando la profundidad crece igual que el dato. Recorrer una lista enlazada de
un millon de nodos son un millon de marcos y un StackOverflowError.
Un arbol balanceado de un millon de nodos son 20 marcos. La pregunta no es
cuantos datos hay, sino que tan hondo llega la estructura.
Con esto claro, sigue con los nueve niveles, o vete directo a la practica si prefieres aprender moviendo la pila con las manos.