Que es, que no es, y para que sirve
Antes de los nueve niveles conviene resolver tres dudas que casi ningun curso responde: que cuenta como recursion, cuando conviene de verdad, y en que programas que usas todos los dias hay recursion adentro.
La definicion, sin adornos
Un metodo es recursivo cuando se llama a si mismo sobre un problema mas pequeno, y existe al menos un caso en el que responde sin volver a llamarse.
Las dos piezas obligatorias
Si falta cualquiera de las dos, no tienes una recursion: tienes un programa roto. Vale la pena aprenderselas asi, en dos frases.
Al menos una entrada para la cual el metodo responde de una, sin llamarse otra vez. Es el piso. Sin piso, la caida no termina nunca.
if (n == 0) return 0; // aqui paro
Cada llamada tiene que recibir un problema estrictamente mas pequeno. Tener piso no basta si nunca caminas hacia el.
return n + suma(n - 1); // n-1, no n
Ponte a prueba antes de seguir
Casi todo el mundo confunde repetir con volver a entrar. Un bucle repite, y no es recursion. Mira estos cinco fragmentos y decide.
Entonces, cuando conviene?
Esta es la pregunta que importa en el trabajo, y la respuesta no es "siempre" ni "nunca". Depende de la forma del problema. Aqui tienes cinco casos resueltos de las dos maneras, para que compares.
Si te quedas con una sola idea de esta pagina, que sea esta: la recursion es segura cuando la profundidad de la pila crece mucho mas despacio que el tamano del dato. Un arbol balanceado de un millon de nodos tiene 20 niveles. Una lista de un millon de nodos tiene un millon.
Los once casos completos, con el codigo comentado de las dos versiones y una tabla de que se optimizo en cada uno, estan en Sin y con recursion.
Donde hay recursion sin que la veas
Esto no es un ejercicio de clase. Casi todo lo que abres en un dia tiene recursion adentro, justamente porque los datos del mundo real vienen anidados.
Un objeto puede tener objetos adentro, sin limite. La libreria que lo parsea es recursiva, obligatoriamente.
Buscar en una carpeta y sus subcarpetas. Windows, Android y tu terminal hacen esto miles de veces al dia.
El DOM de una pagina es un arbol. Dibujarla, calcular estilos y buscar un elemento son recorridos recursivos.
Analizar (2 + (3 * 4)) exige una gramatica
recursiva: una expresion puede contener otra expresion.
Mergesort y quicksort son divide y venceras. El
sort() de casi cualquier lenguaje usa alguno de los dos.
Explorar jugadas es backtracking puro: probar, evaluar la posicion resultante, deshacer y probar otra.
El historial es una pila, la misma estructura que usa la recursion. No es coincidencia.
El arbol de Huffman, que esta detras del ZIP, se construye y se recorre recursivamente.