Recursividad

¿Qué es la recursividad?

En términos simples, es algo que ocurre cuando se "algo" se invoca a sí mismo. Si hablas con un informático, te va a decir que es cuando una función es llamada a sí misma. Pero, es una respuesta algo limitada. 

Es una forma de resolver problemas, una nueva forma de pensar. Es la idea de definir entidades en términos de sí mismos.

En el colegio nos decían que, si querías definir un concepto, no podías utilizar esa misma palabra dentro de la definición, La recursividad es justamente eso.

El caso base

Cuando uno quiere diseñar un algoritmo de manera recursiva, cómo un método se va a invocar a sí mismo, no puede hacerlo infinitas veces, en algún se debe detener. Bueno, el algoritmo para en estos llamados casos bases. 

Son instancias del problema que se pueden resolver de manera inmediata sin necesidad de invocar a la función. Aquellos casos más sencillos en los que no se necesita aplicar la recursividad.

Veamos un ejemplo, la función factorial

Indicamos el factorial de n como n!. Sería el producto de los enteros desde 1 hasta n. Veamos el factorial de 5! que es equivalente a 1 * 2 * 3 * 4 * 5, o 120.

Puedes preguntarte por qué nos podría importar la función factorial. Es muy útil para cuando estamos tratando de contar de cuántas maneras diferentes podemos ordenar cosas o de cuántas maneras diferentes podemos combinar cosas. Por ejemplo, ¿de cuántas maneras diferentes podemos acomodar $�$n cosas? Tenemos $�$n opciones para la primera cosa. Para cada una de esas $�$n opciones, nos quedamos con $�-1$n, minus, 1 opciones para la segunda cosa, de modo que tenemos $�\cdot (�-1)$n, dot, left parenthesis, n, minus, 1, right parenthesis opciones para las dos primeras cosas, en orden. Ahora, para cada una de estas dos primeras opciones, tenemos $�-2$n, minus, 2 opciones para la tercera cosa, dándonos $�\cdot (�-1)\cdot (�-2)$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis opciones para las tres primeras cosas, en orden. Y así sucesivamente, hasta que llegamos a solo dos cosas restantes, y después a una sola cosa restante. Todo junto, tenemos $�\cdot (�-1)\cdot (�-2)\cdots 2\cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis, \@cdots, 2, dot, 1 formas en que podemos ordenar $�$n cosas. Y ese producto es simplemente $�!$n, ! ($�$n factorial), pero con el producto escrito desde $�$n hasta 1 en vez de ir desde 1 hasta $�$n.

La función factorial está definida para todos los enteros positivos, junto con el 0. ¿Qué valor debe tener 0! ? Es el producto de todos los enteros mayores o iguales que 1 y menores o iguales que 0. Pero no hay tales enteros. Por lo tanto, definimos que 0! equivale a la identidad multiplicativa, que es 1. (Definir 0! = 1 empata bien con la fórmula para escoger $�$k cosas de $�$n cosas. Supón que queremos saber cuántas maneras hay para escoger $�$n cosas de $�$n cosas. Eso es fácil, porque solo hay una manera: escoge todas las $�$n cosas. Así que ahora sabemos que, usando nuestra fórmula, $�!\mathrm{/}(�!\cdot (�-�)!)$n, !, slash, left parenthesis, n, !, dot, left parenthesis, n, minus, n, right parenthesis, !, right parenthesis debe ser igual a 1. Pero $(�-�)!$left parenthesis, n, minus, n, right parenthesis, ! es 0!, así que ahora sabemos que $�!\mathrm{/}(�!\cdot 0!)$n, !, slash, left parenthesis, n, !, dot, 0, !, right parenthesis debe ser igual a 1. Si cancelamos el $�!$n, ! tanto en el numerador como en el denominador, vemos que $1\mathrm{/}(0!)$1, slash, left parenthesis, 0, !, right parenthesis debe ser igual a 1, y sí lo es porque 0! es igual a 1).

Así que ahora tenemos una manera de pensar acerca de $�!$n, !. Es igual a 1 cuando $�=0$n, equals, 0, y es igual a $1\cdot 2\cdots (�-1)\cdot �$1, dot, 2, \@cdots, left parenthesis, n, minus, 1, right parenthesis, dot, n cuando $�$n es positivo.

Divide y conquistarás

Cuando se diseña un algoritmo recursivo se recomienda seguir una serie de pasos: 

    1. El caso base 

    2. El concepto de inducción

Consiste en construir la solución de un problema, partiendo de soluciones a problemas más sencillos. Ahora, ¿Qué sería soluciones a problemas más sencillos?

Con un ejemplo se entenderá mejor:

    Supongamos que queremos ordenar una lista de n elementos, bueno, un problema más simple es ordenar una lista de (n - 1) elementos.

La descomposición del problema consiste en considerar estas instancias más pequeñas del mismo problema.

Luego, uno aplica lo que se llama inducción, que es (dicho de manera sencilla) construir la solución completa asumiendo que se conoce las soluciones a problemas más sencillos. 

La elección de que subproblemas se va a utilizar para esa solución es decisión e intuición tuya. Se puede intentar dividir el problema en dos. Considerarlo en (n - 1), (n - 2). Cualquier subproblema es válido siempre que te vayas acercando al caso base. 

¿Recursión o Iteración?

Cómo la recursión es otra forma de pensar, nos podemos llegar a preguntar, ¿Qué es más conveniente usar, recursión o iteración?

¿Qué estrategia elegir para solucionar un problema?

Primero cabe aclarar, que cualquier algoritmo iterativo se puede transformar en recursivo y viceversa. 

A la hora de elegir, un consejo es, si el algoritmo tiene una estructura lineal, digamos estructura de datos de tipo arrays o matriz, empezaría contemplando algoritmos iterativos.

Pero, si los datos o la estructura del problema tiene más forma de árbol o de grafo, es probable que la recursividad sea una buena opción. 

Si uno implementa una solución recursiva y la función que uno diseña solo contiene una llamada recursiva, entonces la estructura que se le llama "el árbol de recursión" o la estructura del proceso recursivo es lineal, se lleva haciendo una llamada, luego otra y otra y otra... O sea, el método siempre hace solamente una llamada recursiva. En esos casos, optaría por la iteración.

Si bien, la recursividad viene bien en ciertos casos, también tiene sus desventajas. Es un poco menos eficiente y, por otro lado, puede dar algún problema relacionado con la pila del sistema. 

Por la propia naturaleza de la recursión, si uno hace muchas llamadas en un proceso lineal, puede acabar teniendo un error en tiempo de ejecución llamado stack over flow, desbordamiento de pila. 

Si el proceso tiene ya dos o más llamados, es más recomendable usar la recursividad y seguramente se obtenga un algoritmo mucho más sencillo de entender. 

También, se puede usar las dos, por el método de BackTracking.

Finalizando

La recursividad es mucho más profunda que este pequeño blog. Es una forma de solucionar problemas y hay muchos más métodos. Mi recomendación es que profundices, veas más ejemplos donde se utilice recursión y resuelvas problemas en el lenguaje que más te guste. 

Gracias por leer, saludos.