La recursión nos permite solucionar problemas que se pueden dividir en casos cada vez más simples.
Por ejemplo, el factorial de un número es la multiplicación de los números (positivos) menores a ese número. La notación que se utiliza para representar el factorial es el número seguido de un signo de exclamación (!). Por ejemplo 5! es igual a 120:
1
5! = 5 * 4 * 3 * 2 * 1 = 120
Copied!
Sin embargo, 5! también se podría expresar como:
1
5! = 5 * 4!
Copied!
Esto es recursión: solucionamos primero 4! y después lo multiplicamos por 5. Pero para solucionar 4! podemos solucionar primero 3! y multiplicarlo por 4. Y para solucionar 3! podemos solucionar 2! y multiplicarlo por 3. Y lo mismo con 2!: solucionamos 1! y lo multiplicamos por 2. El caso base es 1! que es 1.
La clave de la recursión es que una función se puede llamar a sí misma como en el siguiente ejemplo que nunca terminaría:
1
functionhola(){
2
hola();
3
}
4
hola();
Copied!
Cualquier ciclo se puede reescribir de forma recursiva y viceversa. Por ejemplo, podemos imprimir los números del 1 al 10 de forma recursiva:
1
functionprintNumber(x){
2
console.log(x);// imprime el número
3
if(x <10){printNumber(x +1);}
4
}
5
printNumber(1);// inicia la recursión
Copied!
La última línea llama el método printNumber pasándole como parámetro el número 1. Luego, en la línea 2 imprimimos el número y por último la función se llama a si misma si el número es menor a 10.
El ejemplo anterior sería mucho más fácil con un ciclo normal:
1
for(var i=1; i <=10; i++){
2
console.log(x);
3
}
Copied!
Algunos problemas se adaptan mejor a ser solucionados por recursión y otros por iteración.
Lo que debes tener en cuenta al crear una función recursiva es lo siguiente:
1.
Definir los casos triviales, es decir, los casos en los que no se debe volver a invocar la función.
2.
Definir los casos generales, es decir, los casos en los que sí se debe volver a invocar la función.
3.
Verificar que los valores que se pasan como argumentos de la función cambien cada vez que se invoca (se deberían acercar a los casos triviales).