{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Recursión\n",
"\n",
"## Definición\n",
"\n",
"La recursividad se puede definir como la capacidad de una función para construir su respuesta usándose a si misma. La RAE define ``recursivo`` de la siguiente manera:\n",
"\n",
"Dicho especialmente de un proceso: Que se aplica de nuevo al resultado de haberlo aplicado previamente\n",
"\n",
"La recursión es una técnica de programación y matemática, se usa para problemas con la siguiente estructura: [Teoria](http://nbviewer.jupyter.org/github/ProgramacionCompetitivaUNI/ProgramacionCompetitivaUNI/blob/master/no-fiis/clase-09/clase-09.ipynb)\n",
"\n",
"\n",
"\n",
"## Recursión Matemática\n",
"\n",
"Toda recursión matemática debe estar compuesta por 2 elementos principales:\n",
"\n",
"- Conjunto de parámetros: Elementos con los cuales se trabaja para hallar la respuesta\n",
"- Definición de la recursión: Proceso que se sigue para hallar la respuesta\n",
"\n",
"Inclusive, la **definición** de la recursión tiene 2 subelementos:\n",
"\n",
"- Casos base: Casos que ya no necesitan de la función para dar su respuesta\n",
"- Predicado y recursión: Explicación de la función a resolver y la manera en cómo se logra hacerlo.\n",
"\n",
"Por ahora todo parece relativamente confuso, pero veamos el caso más simple de recursión: **El factorial**.\n",
"\n",
"La función factorial (que se expresa como \"$x!$ se lee como factorial de x\") está definida de la siguiente forma para los números enteros no negativos:\n",
"\n",
"$$ n! = \\left\\{ \\begin{array}{cc} 1 &n=0 \\\\ n\\cdot (n-1)! &\\text{en otro caso} \\\\ \\end{array} \\right. $$\n",
"\n",
"En este caso, ``f(x) = x!`` (donde $x$ es el conjunto de parámetros), siendo $f(0) = 1$ como caso base y $f(n) = n\\cdot f(n-1)$ nuestra recursión para $n \\geq 1$. Además, a pesar de ser obvio, el predicado de $f$ es \"$f(x)$ da como respuesta el producto de los numeros naturales entre el 1 y $x$\".\n",
"\n",
"\n",
"### Las Torres de Hanoi\n",
"\n",
"Para introducir una manera un poco más formal de analizar las recursiones, veremos el conocido problema de las torres de hanoi, el cual señala lo siguiente:\n",
"\n",
"- Tenemos 3 postes fijos.\n",
"\n",
"- En uno de los postes hay 64 discos colocados con un tamaño descreciente desde la base hasta el tope.\n",
"\n",
"- En un movimiento, podemos llevar un disco del tope de alguno de los postes a otro poste que esté vacio o que el tamaño del primer disco de este sea mayor que el que moveremos.\n",
"\n",
"- El problema pide mover la torre de discos inicial y colocarlos de esa manera en otro poste.\n",
"\n",
"La idea es resolver este problema en la menor cantidad de tiempo posible, por lo que debemos determinar la mínima cantidad de movimientos posibles.\n",
"\n",
"Para resolver recursiones, siempre es bueno ver los casos pequeños para buscar un patrón. En este caso, vamos a generalizar: En vez de 64 discos, supongamos que hay $n$ discos.\n",
"\n",
"Entoncs, definimos la función $T(n)$ que nos dará la cantidad mínima de movimientos que se deben usar para resolver el problema con $n$ discos.\n",
"\n",
"Claramente, los casos más pequeños y lógicos serían:\n",
"\n",
"- $T(0) = 0$, no hay necesidad de movimientos si no hay discos\n",
"\n",
"- $T(1) = 1$, basta con colocar directamente el disco en el poste deseado\n",
"\n",
"- $T(2) = 3$, disco 1 -> poste 2, disco 2 -> poste 3, disco 1 -> poste 3\n",
"\n",
"Ahora, esta función poco a poco toma cierta forma, pero veamos matemáticamente los límites de la función $T$:\n",
"\n",
"Para mover $n$ discos a otro poste, por la naturaleza del problema, debemos mover la torre de $n-1$ discos superiores antes del $n$-ésimo disco a otro poste, luego movemos este disco al poste deseado y finalmente movemos los otros $n-1$ discos a la torre deseada. Esto se puede denotar como:\n",
"\n",
"$ T(n) \\leq T(n-1) + 1 + T(n-1) $\n",
"\n",
"$ T(n) \\leq 2T(n-1) + 1 $\n",
"\n",
"Ahora probamos el límite superior; pero si nos damos cuenta, la única situación en la que no se hacen movimientos innecesarios es la explicada anteriormente, pues necesitamos:\n",
"\n",
"1) Al menos un poste esté libre\n",
"\n",
"2) Salida sin problemas para el $n$-ésimo disco\n",
"\n",
"Por lo que esto se logra solamente si todos los otros $n-1$ discos están en un poste diferente al original, y por las condiciones, deben estar en forma de torre decreciente de la base al tope, entonces llegamos a que:\n",
"\n",
"$$ T(n) \\geq T(n-1) + 1 + T(n-1) $$\n",
"\n",
"$$ T(n) \\geq 2T(n-1) + 1 $$\n",
"\n",
"Juntando ambas desigualdades y el caso base $T(0)=0$, llegamos a que:\n",
"\n",
"$$ T(0) = 0 $$\n",
"\n",
"\n",
"\n",
"$$ T(n) = 2T(n-1)+1, n\\geq 1 $$\n",
"\n",
"Esta recursión se ve similar a la función $f(n) = 2^{n}-1$, pero no estamos completamente seguros a menos que demostremos su veracidad. Probemos por inducción:\n",
"\n",
"1) $T(0) = f(0) = 2^{0}-1 = 0$\n",
"\n",
"2) $T(n) = f(n) = 2^{n}-1$\n",
"\n",
"3) $T(n+1) = 2T(n) + 1 = 2(2^{n}-1)+1 = 2^{n+1}-2+1 = 2^{n+1}-1$ -> Probamos la igualdad de ambas funciones.\n",
"\n",
"Sin embargo, la meta de las recursiones no es adivinar la relación, sino ser más precisos y obtener conclusiones sin tener que jugar con nuestra suerte. Para evitar ello, plantearemos una manera más sencilla de analizar las recursiones separando por casos más adelante.\n",
"\n",
"### Problema de Josephus\n",
"\n",
"Este problema señala que se colocarán $n$ personas en un círculo, de manera horaria, y en una ronda se eliminan cada 2 personas de las que están presentes. Se repiten las rondas hasta que solo quede una persona. Debemos determinar el número de la persona que queda.\n",
"\n",
"Una idea intuitiva, para empezar, es que la respuesta nunca será un número par, pues todos ellos son eliminados en la primera ronda.\n",
"\n",
"Definamos la función $J(n)$ como la que nos dará la respuesta para $n$ personas.\n",
"\n",
"Ahora, veamos los casos más pequeños:\n",
"\n",
"| n | 1 | 2 | 3 | 4 | 5 | 6 |\n",
"|------|---|---|---|---|---|---|\n",
"| J(n) | 1 | 1 | 3 | 1 | 3 | 5 |\n",
"\n",
"Ciertamente, no parece que haya un patrón estricto, tal vez es una repetición de 1 -> 1,3 -> 1,3,5 -> 1,3,5,7 -> ..., pero esto no nos ayuda a darle forma matemática al problema.\n",
"\n",
"Veamos el caso para $n=2k$:\n",
"\n",
"- Hay $2k$ personas inicialmente.\n",
"\n",
"- En la siguiente ronda han sido eliminadas todas las personas $2i$ y quedan las que tienen numeros $2i+1$.\n",
"\n",
"- Observación 1: La cantidad de personas ha sido reducida a $k$.\n",
"\n",
"- Observación 2: Ahora hay $k$ personas, pero sus números son 1,3,5,7,...,2i-1, por lo que la posición de la persona que se salva es igual a $J(k)$ pero su número para $J(2k)$ será $2J(k)-1$ por la biyección que se puede plantear.\n",
"\n",
"Con lo anterior, llegamos a que:\n",
"\n",
"$$ J(2k) = 2J(k)-1, k\\geq 1 $$\n",
"\n",
"Ahora, supongamos $n=2k+1$:\n",
"\n",
"- Hay $2k+1$ personas inicialmente.\n",
"\n",
"- En la siguiente ronda han sido eliminadas todas las personas $2i$, pero con un paso más se elimina también la persona con número $1$ luego de la persona $2k$.\n",
"\n",
"- Observación 1: La cantidad de personas ha sido reducida a $k$.\n",
"\n",
"- Observación 2: Ahora hay $k$ personas, pero sus números son 3,5,7,...,2i+1, por lo que la posición de la persona que se salva es igual a $J(k)$, pero su número para $J(2k+1)$ será $2J(k)+1$.\n",
"\n",
"Con lo anterior, llegamos a que:\n",
"\n",
"$$ J(2k+1) = 2J(k)+1, k\\geq 1 $$\n",
"\n",
"Entonces, con el caso base $J(1) = 1$ tenemos:\n",
"\n",
"$$ J(n) = \\left\\{ \\begin{array}{cc} 1 &n=1 \\\\ 2J(k)-1 &n=2k, k > 0 \\\\ 2J(k)+1 &n=2k+1, k > 0 \\end{array} \\right. $$\n",
"\n",
"\n",
"Aun no parece muy clara la recursión, veamos (ahora que nos es más sencillo) varios de los casos pequeños:\n",
"\n",
"| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |\n",
"|------|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|\n",
"| J(n) | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 |\n",
"\n",
"Se ve claramente que se va tomando los primeros $2^{i}$ numeros impares y se repite el proceso aumentando $i$ en 1.\n",
"\n",
"Ahora, notemos que siempre la respuesta es 1 cuando $n = 2^{k}$, y por lo que nos hemos dado cuenta sobre las respuestas, el último número que no tendrá respuesta igual a 1 y que sea mayor que $n$ es precisamente $m=2^{k+1}-1$, pues para llegar al siguiente 1 aumentaríamos $2^{k}$, y basta con restar 1 para obtener el anterior. Entonces, se da la secuencia de los $2^{k}$ primeros números impares desde $n=2^{k}$ hasta $m=2^{k+1}-1$.\n",
"\n",
"Ahora, si nos damos cuenta, la secuencia de respuestas y sus parámetros están ordenadas, y además lo único que tienen diferente todos los números desde el $n$ hasta el $m$ son los bits hasta el de orden $k-1$. Ahora se nos puede ocurrir pensar en algo como que:\n",
"\n",
"Si $n = 2^{m} + l$, entonces su respuesta es la posición $l$ (con indexación desde 0) de los primeros impares, la cual sería $2l+1$, con $0 \\leq l < 2^{m}$.\n",
"\n",
"Esto parece tener sentido debido al patrón y a nuestras observaciones, pero demostremos inductivamente que de verdad es la solución:\n",
"\n",
"- $J(1) = f(2^{0}+0) = 2(0)+1 = 1$.\n",
"\n",
"- $J(2^{m}+l) = 2l+1$.\n",
"\n",
"- Supongamos para $n=2^{m}+2k$ par:\n",
"\n",
" 1) $J(n) = 2J(\\frac{n}{2})-1 = 2(2^{m-1}+k)-1 = 2(2k+1)-1 = 4k+1 = 2(2k)+1$, cumple cuando $l$ es par.\n",
"\n",
"- Supongamos para $n=2^{m}+2k+1$ impar:\n",
" \n",
" 1) $J(n) = 2J(\\frac{n}{2})+1 = 2(2^{m-1}+k)+1 = 2(2k+1)+1 = 4k+3 = 2(2k+1)+1$, cumple cuando $l$ es impar.\n",
"\n",
"\n",
"### Problemas propuestos\n",
"\n",
"1) ¿Cuál es la máxima cantidad de regiones que se pueden formar colocando $n$ rectas en un plano?\n",
"\n",
"2) Igual que el problema 1, pero esta vez no son rectas, sino lineas infinitas en forma de zig-zag (Como una V rotada e infinita en extensión) \n",
"\n",
"3) Halle la solución para las Torres de Hanoi pero si se da que los movimientos directamente del poste $A$ (original) al $C$ (deseado) no son válidos.\n",
"\n",
"## Fractales\n",
"\n",
"Los fractales son estructuras matemáticas cuya construcción se define por una profundidad como parámetro y un proceso recursivo.\n",
"\n",
"Son un área de estudio relativamente reciente en las matemáticas, y por su comportamiento, inspira la curiosidad de muchas personas. Este caso no es diferente para programación competitiva, pues existen una cantidad considerable de problemas relacionados con estos.\n",
"\n",
"### Copo de nieve de Koch\n",
"\n",
"1) Se toma un segmento\n",
"\n",
"2) Dividir cada segmento en 3 partes iguales, reemplazar la parte central por dos partes iguales formando un ángulo de 60 grados. Repetir hasta llegar a la profundidad deseada\n",
"\n",
"\n",
"\n",
"Los problemas principalmente tratarán de construir un fractal dado su procedimiento o de intentar analizar cada uno de sus pasos.\n",
"\n",
"Veamos estos 4 problemas de recursión.\n",
"\n",
"- [Fit Squares in Triangle - Easy](https://www.codechef.com/problems/TRISQ)\n",
"\n",
"- [Fractal - Easy](http://www.spoj.com/problems/URJC2_F/)\n",
"\n",
"- [All Squares - Easy/Medium](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=91)\n",
"\n",
"- [Connecting Soldiers - Medium](https://www.codechef.com/problems/NOKIA)\n",
"\n",
"## Fast Exponentiation\n",
"\n",
"Esta es una manera de optimizar una exponenciación, la cual naturalmente se haría en $O(b)$ siendo $a$ la base y $b$ el exponente, para lograrla en $O(\\log{b})$. La idea principalmente es barrer los bits de $b$:\n",
"\n",
"Supongamos que la representación binaria de $b$ es la siguiente:\n",
"\n",
"$$ b = b_{k}b_{k-1}\\ldots b_{2}b_{1}b_{0} $$\n",
"\n",
"Entonces podemos representar:\n",
"\n",
"$$ a^{b} = a^{b_{k}\\cdot2^{k} + b_{k-1}\\cdot2^{k-1} + \\ldots + 2\\cdot b_{1} + b_{0}} $$\n",
"\n",
"Por lo cual podemos plantear lo siguiente:\n",
"\n",
"$$ a^{b} = a^{b_{0}}\\cdot \\left(a^{2}\\right)^{b_{k}b_{k-1}\\ldots b_{2}b_{1}} $$\n",
"\n",
"Entonces definimos la función $fast\\_exp(a,b)$ como la que nos dará el resultado de $a^{b}$:\n",
"\n",
"$$ fast\\_exp(a,b) = a^{b} $$\n",
"\n",
"Pero por lo que planteamos hace un momento, debemos ver el siguiente patrón:\n",
"\n",
"$$ fast\\_exp(a,b) = a^{b mod 2} \\cdot fast\\_exp(a^{2},b/2) $$\n",
"\n",
"Donde $b/2$ es el cociente entero de la división de $b$ entre 2.\n",
"\n",
"De esta recursión, recordando además que $fast\\_exp(a,0) = 1$, podemos plantear el siguiente código:\n",
"\n",
"```Cpp\n",
"long long fast_exp(long long a, int b){\n",
" if(b == 0) return 1LL; // Caso base\n",
" if(b % 2 == 0) return fast_exp(a*a,b/2); // Si el bit de orden 0 está apagado\n",
" return a*fast_exp(a*a,b/2); // Si el bit de orden 0 esta prendido\n",
"}\n",
"```\n",
"\n",
"Algo beneficioso de esta función es que se puede aplicar a cualquier operación que sea asociativa en repetición, como la suma, coseno de la suma de dos angulos, etc.\n",
"\n",
"## Maximo Comun Divisor\n",
"\n",
"La idea instintiva para hallar el MCD de dos numeros $a$ y $b$ es iterar desde 1 hasta el minimo entre ambos y actualizar cada vez que encontramos un numero que divida a ambos, pero esto tiene una complejidad de $O(min(a,b))$, lo cual no es muy eficiente si usamos números hasta $10^{18}$. Para solucionar este problema, usaremos el algoritmo de Euclides, el cual usa la siguiente recusión (considerando $a \\geq b$):\n",
"\n",
"$$ gcd(a,0) = a $$\n",
"$$ gcd(a,b) = gcd(b,a mod b) $$\n",
"\n",
"Ahora, la veracidad del funcionamiento del algoritmo está demostrada, pero ¿Qué hay de su complejidad?.\n",
"\n",
"Para hallar un estimado de su complejidad debemos hallar lo que sucede en cada paso:\n",
"\n",
"$$ gcd(a,b) \\rightarrow (a,b) $$\n",
"$$ gcd(b,a mod b) \\rightarrow (b,q),\\text{ si } a = bk+q $$\n",
"\n",
"Y así se da de manera consecutiva. Sin embargo, notemos que el peor de los casos se debería dar cuando $a$ se reduce en lo mínimo posible; y al ser $a \\geq b$, se da cuando $a = b+q$. De manera similar, $b = q+r$ y así consecutivamente. Si lo colocamos de una manera más fácil de ver, sería:\n",
"\n",
"Si fijamos la solución final:\n",
"\n",
"$$ 0 \\rightarrow m \\rightarrow n=m \\rightarrow s=m+n \\rightarrow \\cdots \\rightarrow b=q+r \\rightarrow a=b+q $$\n",
"\n",
"Notamos que si colocamos la recursión de esta manera (tal que cada paso es tomar dos numeros consecutivos y colocarlos adecuadamente en los parámetros), se parece muchísimo a la sucessión de **Fibonacci**.\n",
"\n",
"Ciertamente, el peor de los casos se dará cuando $a$ y $b$ son números de Fibonacci consecutivos, en cuyo caso, si $a = F_{n}$ y $b = F_{n-1}$, la siguiente llamada a la función dará $a=F_{n-1}$ y $b=F_{n-2}$ como parámetros, realizando unas $n-1$ iteraciones con la función.\n",
"\n",
"Con lo anterior, tenemos que $gcd(F_{n},F_{n-1}) = \\Theta(n)$ y para cualquier número $a$, $gcd(a,F_{n-1}) = O(n)$. Dado que $F_{n-1} = \\Theta(\\varphi^{n})$, esto implica aproximadamente que $gcd(a,b) = O(\\log_{\\varphi}{b})$ pero al ser $\\varphi > 2$, entonces también se da que $gcd(a,b) = O(\\log_{2}{b})$"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.1"
}
},
"nbformat": 4,
"nbformat_minor": 2
}