Explorando la recursión

El objetivo de esta lección es introducir a los estudiantes al concepto de recursión, entender sus fundamentos y dominar su implementación en programación. Al final de esta lección, los estudiantes deberían ser capaces de:

• Definir recursión y sus características clave.

• Entender la mecánica de las funciones recursivas.

• Implementar algoritmos recursivos básicos.

• Identificar escenarios adecuados para la recursión.

Introducción:

• Comenzar con una breve discusión sobre técnicas de resolución de problemas en programación.

• Introducir el concepto de recursión con un ejemplo de la vida real.

• Definir la recursión como una técnica de programación donde una función se llama a sí misma directa o indirectamente para resolver un problema.

• Destacar las características clave de la recursión: caso base, caso recursivo y auto-referencia.

Entendiendo las Funciones Recursivas:

• Explicar la mecánica de las funciones recursivas usando un ejemplo simple (factorial, potencia $x^n$ o secuencia de Fibonacci).

• Demostrar cómo funcionan las funciones recursivas paso a paso, enfatizando la importancia del caso base.

• Discutir la pila de llamadas y cómo se utiliza en las llamadas de funciones recursivas.

• Aclarar el concepto de recursión infinita y cómo evitarla.

Implementando Algoritmos Recursivos:

• Presentar una serie de problemas de programación adecuados para la recursión.

• Dividir a los estudiantes en pares o grupos pequeños para resolver estos problemas usando recursión.

• Animar a los estudiantes a escribir funciones recursivas desde cero, enfocándose en definir el caso base y el caso recursivo.

• Circular entre los grupos para proporcionar orientación y asistencia según sea necesario.

Revisión y Práctica:

• Hacer que cada grupo presente sus soluciones recursivas a la clase.

• Discutir la eficiencia y legibilidad de los diferentes enfoques recursivos.

• Abordar cualquier desafío común o conceptos erróneos encontrados durante el ejercicio.

• Proporcionar problemas de práctica adicionales para que los estudiantes trabajen individualmente o en grupos.

Conclusión:

• Resumir los puntos clave cubiertos en la lección, enfatizando el poder y la versatilidad de la recursión en programación.

• Animar a los estudiantes a seguir explorando la recursión en sus propios proyectos y asignaciones.

Tarea:

• Asignar ejercicios de tarea para reforzar los conceptos aprendidos en clase, como implementar algoritmos recursivos para problemas específicos o analizar funciones recursivas existentes en bibliotecas de código.

Evaluación:

• Evaluar la comprensión de los estudiantes a través de su participación en discusiones en clase, su capacidad para resolver problemas de programación recursiva y su claridad al explicar soluciones recursivas.

• Revisar las tareas para evaluar el dominio individual de los conceptos y habilidades de implementación de la recursión.

Introducción

Comenzar con una breve discusión sobre técnicas de resolución de problemas en programación

En programación, la resolución de problemas es una habilidad fundamental que utilizarás cada vez que escribas código. Antes de sumergirnos en los detalles de la recursión, tomemos un momento para hablar sobre técnicas de resolución de problemas.

Piensa en la resolución de problemas como un viaje. Comienzas con un problema — una tarea que deseas que tu programa realice — y necesitas averiguar cómo llegar desde el punto A (el problema) al punto B (la solución). Este viaje implica descomponer el problema en piezas más pequeñas y manejables, entender las reglas o restricciones involucradas y diseñar un plan para alcanzar el resultado deseado.

Existen varias técnicas que los programadores utilizan para abordar problemas de manera efectiva. Aquí hay algunas claves:

• Entender el Problema: Antes de poder resolver un problema, necesitas comprenderlo completamente. Esto implica leer y analizar la declaración del problema, identificar las entradas y salidas y aclarar cualquier incertidumbre.

• Divide y Vencerás: Muchos problemas complejos pueden resolverse dividiéndolos en subproblemas más pequeños y manejables. Este enfoque, conocido como divide y vencerás, te permite abordar cada subproblema por separado y luego combinar las soluciones para resolver el problema más grande.

• Pensamiento Algorítmico: Los algoritmos son procedimientos paso a paso para resolver problemas. Cuando te enfrentas a un problema, intenta pensar algorítmicamente descomponiendo la solución en una secuencia de pasos lógicos.

• Abstracción: La abstracción implica centrarse en los detalles esenciales de un problema mientras ignoras la información irrelevante o distraída. Al abstraer los detalles innecesarios, puedes simplificar el problema y concentrarte en lo que es importante.

• Iteración y Recursión: La iteración implica resolver un problema mediante la ejecución repetida de un bucle o secuencia de instrucciones. La recursión, por otro lado, implica resolver un problema dividiéndolo en instancias más pequeñas del mismo problema. Tanto la iteración como la recursión son técnicas poderosas de resolución de problemas que encontrarás frecuentemente en programación.

Al dominar estas técnicas de resolución de problemas, estarás mejor equipado para abordar una amplia gama de desafíos de programación, incluidos aquellos que implican recursión. Así que, a medida que exploramos la recursión con más profundidad, mantén estas estrategias de resolución de problemas en mente — te servirán como herramientas valiosas en tu caja de herramientas de programación.

Introduce el concepto de recursión con un ejemplo de la vida real

Muy bien, retrocedamos un poco del código por un momento y pensemos en la recursión en términos de ejemplos de la vida real. Imagina que estás frente a un conjunto de muñecas rusas, también conocidas como muñecas Matryoshka. Estas muñecas vienen en varios tamaños, cada una encajando dentro de la siguiente más grande.

Ahora, pensemos en cómo podríamos describir el proceso de abrir cada muñeca en el conjunto. Comienzas con la muñeca más grande y, al abrirla, encuentras una muñeca más pequeña anidada dentro. Luego abres esa muñeca más pequeña, solo para descubrir una aún más pequeña dentro, y así sucesivamente, hasta que llegas a la muñeca más pequeña — la que no contiene ninguna otra.

Este proceso de abrir cada muñeca puede considerarse recursivo. ¿Por qué? Porque cada muñeca es similar en estructura a las demás, y la acción de abrir una muñeca es la misma para cada una – implica mirar dentro para ver si hay una muñeca más pequeña anidada dentro.

En términos de programación, la recursión funciona de manera similar. En lugar de abrir muñecas rusas, estamos "abriendo" funciones o métodos. Una función recursiva es una que se llama a sí misma, ya sea directamente o indirectamente, para resolver un problema descomponiéndolo en instancias más pequeñas del mismo problema.

Entonces, al igual que con las muñecas Matryoshka, la recursión implica abordar un problema descomponiéndolo en subproblemas más pequeños y similares, hasta que llegamos a un punto donde el problema es tan pequeño y simple que podemos resolverlo directamente. Esta versión más pequeña y simple del problema es lo que llamamos el caso base.

Al entender la recursión a través de ejemplos de la vida real como las muñecas rusas, podemos comenzar a ver cómo se aplica a la programación y cómo puede ser una herramienta poderosa para resolver problemas complejos de manera clara y elegante. Así que, mientras profundizamos en la recursión, mantén esta analogía visual en mente — te ayudará a comprender el concepto de manera más intuitiva.

Define la recursión como una técnica de programación donde una función se llama a sí misma directa o indirectamente para resolver un problema

Ahora desglosamos la definición de recursión en términos más simples. Imagina que tienes una función — un conjunto de instrucciones que realiza una tarea específica en tu programa. Ahora, ¿qué tal si te digo que esta función podría llamarse a sí misma? ¡Sí, escuchaste bien! Esto es lo que llamamos recursión.

Recursión es como un bucle, pero en lugar de repetir un conjunto de instrucciones hasta que se cumpla una condición, una función recursiva se repite a sí misma llamándose a sí misma — directa o indirectamente — hasta que alcanza una condición específica, generalmente llamada caso base.

Déjame explicar esto con un ejemplo. Imagina que tienes una función llamada "cuentaRegresiva" que imprime números desde un número dado $n$ hasta $1$. En lugar de usar un bucle, podemos definir "cuentaRegresiva" recursivamente. Así es como funciona:

• La función "cuentaRegresiva" toma un número $n$ como entrada.

• Si el número es $1$ (el caso base), simplemente imprime "$1$" y se detiene.

• Si el número es mayor que $1$, imprime el número actual y luego se llama a sí misma con el siguiente número más pequeño.

• Este proceso continúa hasta que la función alcanza el caso base, momento en el cual deja de llamarse a sí misma y la recursión "se desenvuelve" de vuelta a la llamada original.

def cuentaRegresiva(n):
  # Caso base: si n es 1, imprímelo y detén la recursión
  if n == 1:
    print(n)
  else:
    # Imprimir el número actual
    print(n)
    # Llamar a la función cuentaRegresiva con el siguiente número más pequeño
    cuentaRegresiva(n - 1)

# Ejemplo de uso:
cuentaRegresiva(5)  # Imprime números del 5 al 1

Entonces, en esencia, la recursión es una forma de resolver problemas descomponiéndolos en subproblemas más pequeños y similares, y luego resolviendo esos subproblemas llamando a la misma función una y otra vez hasta que llegamos a un caso base donde el problema se puede resolver directamente.

Ten en cuenta que la recursión puede ser un poco desconcertante al principio, pero con la práctica y la comprensión de sus principios, podrás usarla como una herramienta poderosa en tu arsenal de programación.

Destaca las características clave de la recursión: caso base, caso recursivo y auto-referencia

Ahora que entendemos qué es la recursión y cómo funciona, profundicemos en sus características clave. La recursión es como una máquina bien engrasada — tiene partes específicas que trabajan juntas para que funcione sin problemas. Aquí están las tres características clave de la recursión que destacaremos: caso base, caso recursivo y auto-referencia.

Caso Base:

• Piensa en el caso base como el punto de parada de nuestra función recursiva. Es la condición que le dice a la función cuándo dejar de llamarse a sí misma y comenzar a devolver valores.

• Sin un caso base, nuestra función recursiva seguiría llamándose indefinidamente, lo que lleva a lo que llamamos recursión infinita, ¡lo cual no es lo que queremos!

• En nuestro ejemplo anterior de la función "cuentaRegresiva", el caso base era cuando $n$ se convertía en $1$. En ese momento, simplemente imprimíamos $1$ y dejábamos de llamar a la función.

Caso Recursivo:

• El caso recursivo es donde ocurre la magia de la recursión. Es la parte de nuestra función donde llamamos a la función en sí.

• Cada vez que nuestra función encuentra el caso recursivo, es como dar un paso más hacia el caso base. Estamos descomponiendo el problema en subproblemas más pequeños y más pequeños hasta que alcanzamos el caso base.

• En la función "cuentaRegresiva", el caso recursivo era cuando $n$ era mayor que $1$. Imprimíamos el valor actual de $n$, luego llamábamos a la función "cuentaRegresiva" nuevamente con $n-1$.

Auto-Referencia:

• Esta característica puede sonar elegante, pero es bastante simple. Auto-referencia significa que nuestra función se refiere a sí misma.

• Cuando definimos una función recursiva, esencialmente estamos diciendo: "Oye, función, puedes llamarte a ti misma si es necesario".

• Esta naturaleza auto-referencial es lo que permite a la recursión abordar problemas complejos descomponiéndolos en instancias más pequeñas del mismo problema.

• En la función "cuentaRegresiva", vimos la auto-referencia en acción cuando llamamos a "cuentaRegresiva" dentro de la propia función.

Entonces, para recapitular, la recursión tiene tres características clave:

1. el caso base, que nos dice cuándo detenernos;

2. el caso recursivo, que descompone el problema en subproblemas más pequeños;

3. auto-referencia, que permite que la función se llame a sí misma.

Entender y dominar estas características es esencial para convertirse en un experto en recursión y usarla de manera efectiva en tu viaje de programación.

Entendiendo las Funciones Recursivas

Explica la mecánica de las funciones recursivas usando un ejemplo simple

Desglosemos la mecánica de las funciones recursivas usando el ejemplo de calcular el factorial de un número.

El factorial de un número entero no negativo $n$, denotado como $n!$, es el producto de todos los enteros positivos menores o iguales a $n$. Por ejemplo, $5!$ (leído como "cinco factorial") es igual a $5\cdot 4\cdot 3\cdot 2\cdot 1$, lo que equivale a $120$.

Ahora, implementemos esto usando una función recursiva:

# La función fact calcula el factorial del número n
def fact(n):
  if n == 0: return 1
  return n * fact(n-1)

# La parte principal del programa. Leer el valor de entrada de n
n = int(input())

# Calcular e imprimir la respuesta
print(fact(n))

Ahora, entendamos cómo funciona esta función recursiva:

Caso Base:

• En nuestra función factorial, el caso base es cuando $n$ es igual a $0$. En estos casos, sabemos que el factorial de $0$ es siempre $1$. Así que, devolvemos $1$.

Caso Recursivo:

• Para cualquier otro valor de $n$ (cuando $n$ es mayor que $1$), calculamos el factorial recursivamente. Llamamos a la función factorial con el argumento $n-1$ y multiplicamos el resultado por $n$.

• Esto significa que para calcular $fact(n)$, primero necesitamos calcular $fact(n-1)$, luego multiplicar el resultado por $n$. Este proceso continúa hasta que llegamos al caso base.

Vamos a caminar a través de un ejemplo:

• Si queremos calcular $fact(5)$, la función llamará a $fact(4)$, que llamará a $fact(3)$, y así sucesivamente, hasta llegar al caso base.

• Una vez que alcanzamos el caso base $(fact(1))$, comenzamos a "desenvolver" las llamadas recursivas.

• Cada llamada recursiva devuelve su resultado y lo multiplica por el valor actual de $n$.

• Finalmente, el resultado de $fact(5)$ se calcula como $fact(4)\cdot 5$, que se calcula además como $fact(3)\cdot 4\cdot 5$, y así sucesivamente, hasta que tenemos el resultado final.

Así es como funciona la recursión! Es como pelar capas de una cebolla — una capa a la vez — hasta llegar al núcleo. Y entender este proceso recursivo es crucial para dominar las funciones recursivas en programación.

Demuestra cómo funcionan las funciones recursivas paso a paso, enfatizando la importancia del caso base

Ahora, recorramos cómo funcionan las funciones recursivas paso a paso utilizando el secuencia de Fibonacci como ejemplo. La secuencia de Fibonacci es una serie de números donde cada número es la suma de los dos anteriores, comenzando típicamente con $0$ y $1$. Entonces, la secuencia es: $0,1,1,2,3,5,8,13$, y así sucesivamente.

La secuencia de Fibonacci tiene la siguiente forma:

El mayor número de Fibonacci que cabe en el tipo int es

Para $n\le 40$ es suficiente utilizar el tipo de dato int.

Sea la función $fib(n)$ que calcula el $n$-ésimo número de Fibonacci. Entonces tenemos la siguiente relación de recurrencia:

Ahora, implementemos una función recursiva para calcular los números de Fibonacci:

# La función fib calcula el n-ésimo número de Fibonacci
def fib(n):
  if (n == 0): return 0
  if (n == 1): return 1
  return fib(n - 1) + fib(n - 2)

# La parte principal del programa. Leer el valor de entrada de n
n = int(input())

# Calcular e imprimir la respuesta
print(fib(n))

Ahora, desglosamos cómo funciona esta función recursiva paso a paso:

Caso Base:

• Los casos base son cuando $n$ es $0$ y $1$. En estos casos, sabemos el número de Fibonacci directamente: $F_0=0$ y $F_1=1$. Estos son los casos más simples donde no necesitamos más cálculo.

Caso Recursivo:

• Para cualquier otro valor de $n$ (cuando $n>1$), calculamos el número de Fibonacci recursivamente. Hacemos esto sumando los números de Fibonacci de las dos posiciones anteriores en la secuencia ($fib(n-1)$ y $fib(n-2)$).

• Esto significa que para calcular $fib(n)$, primero necesitamos calcular $fib(n-1)$ y $fib(n-2)$, y luego sumar sus resultados. Este proceso continúa hasta que llegamos a los casos base.

Vamos a caminar a través de un ejemplo:

• Si queremos calcular $fib(4)$, la función llamará a $fib(3)$ y $fib(2)$.

• $fib(3)$ llamará a su vez a $fib(2)$ y $fib(1)$, y $fib(2)$ llamará a $fib(1)$ y $fib(0)$.

• $fib(1)$ y $fib(0)$ son casos base, por lo que devuelven $1$ y $0$, respectivamente.

• Una vez que tenemos los resultados de $fib(1)$ y $fib(0)$, $fib(2)$ los sumará $(0+1=1)$.

• $fib(3)$ sumará de manera similar los resultados de $fib(2)$ y $fib(1)(1+1=2)$.

• Finalmente, $fib(4)$ sumará $fib(3)$ y $fib(2)(2+1=3)$, y obtenemos el resultado $3$.

Este proceso paso a paso demuestra cómo funcionan las funciones recursivas, descomponiendo gradualmente el problema en subproblemas más pequeños hasta llegar a los casos base, y luego combinando los resultados para resolver el problema original. Y como hemos visto, los casos base juegan un papel crucial al detener la recursión y proporcionar los puntos de partida para nuestro cálculo.

Discutir la pila de llamadas y cómo se utiliza en las llamadas de funciones recursivas

Ahora profundicemos en el concepto de la pila de llamadas y cómo se utiliza en las llamadas de funciones recursivas. Imagina la pila de llamadas como una pila de platos en una cafetería. Cuando entras en la cafetería, tomas un plato y lo agregas a la parte superior de la pila. De manera similar, cuando se llama a una función en un programa, se agrega información sobre esa llamada de función a la pila de llamadas.

Veamos cómo funciona esto con llamadas de funciones recursivas:

Llamadas a Funciones y la Pila de Llamadas:

• Cuando se llama a una función, se crea un nuevo marco en la parte superior de la pila de llamadas para almacenar información sobre esa llamada de función. Esto incluye los parámetros de la función, las variables locales y la dirección de retorno — el punto en el programa donde debe continuar la ejecución después de la llamada a la función.

• Cada vez que se llama a una nueva función (ya sea una llamada recursiva o una llamada a una función regular), se agrega un nuevo marco a la parte superior de la pila de llamadas.

Llamadas a Funciones Recursivas:

• En el caso de las llamadas a funciones recursivas, la función se llama a sí misma dentro de su propio cuerpo. Esto significa que cada llamada recursiva crea un nuevo marco en la parte superior de la pila de llamadas.

• A medida que la recursión progresa, se agregan más y más marcos a la pila de llamadas, cada uno representando una instancia separada de la llamada a la función.

• La pila de llamadas realiza un seguimiento de todas estas llamadas a funciones, asegurando que el programa sepa dónde regresar después de que cada llamada a la función se complete.

Caso Base y Desenvolver la Pila:

• Eventualmente, a medida que la recursión progresa, se alcanza el caso base. Esta es la condición de detención que evita que la recursión continúe indefinidamente.

• Cuando se alcanza el caso base, la función deja de hacer llamadas recursivas adicionales y comienza a "desenvolver" la pila de llamadas.

• Cada marco se quita de la pila de llamadas, y el programa regresa al punto donde se llamó originalmente a la función. Este proceso continúa hasta que se desenrolla toda la pila de llamadas.

Consideraciones de Memoria:

• Es importante tener en cuenta que la pila de llamadas tiene un tamaño limitado, y la recursión excesiva puede llevar a un error de desbordamiento de pila si la pila se vuelve demasiado profunda.

• Por lo tanto, al escribir funciones recursivas, es crucial asegurarse de que haya un caso base adecuado para evitar la recursión infinita y limitar la profundidad de la recursión para evitar el desbordamiento de la pila.

En resumen, la pila de llamadas juega un papel crucial en la gestión de las llamadas a funciones, incluidas las llamadas a funciones recursivas. Realiza un seguimiento de la secuencia de llamadas a funciones y asegura que el programa sepa dónde regresar después de que cada llamada a la función se complete. Entender la pila de llamadas es esencial para comprender cómo funciona la recursión y para escribir funciones recursivas eficientes y sin errores.

Aclarar el concepto de recursión infinita y cómo evitarla

Ahora aclaremos el concepto de recursión infinita y discutamos cómo evitarla.

Recursión Infinita:

• La recursión infinita ocurre cuando una función recursiva se llama a sí misma indefinidamente sin alcanzar un caso base que detendría la recursión.

• En otras palabras, la función sigue haciéndose llamadas recursivas sin avanzar hacia un caso base, lo que lleva a un bucle infinito de llamadas a funciones.

• Esto puede consumir rápidamente todos los recursos disponibles del sistema y hacer que el programa se bloquee o se cuelgue indefinidamente.

Cómo Ocurre:

• La recursión infinita ocurre típicamente cuando falta un caso base o cuando el caso base es incorrecto en la función recursiva.

• Sin un caso base, o con un caso base que nunca se alcanza debido a una lógica incorrecta, la función seguirá llamándose a sí misma para siempre.

Ejemplo:

Consideremos un ejemplo simple de una función recursiva para contar hacia abajo desde un número dado:

def cuentaRegresiva(n):
  # Imprimir el número actual
  print(n)
  # Llamar a la función cuentaRegresiva con el siguiente número más pequeño
  cuentaRegresiva(n - 1)

# Ejemplo de uso:
cuentaRegresiva(5)  # Imprime números del 5 hasta menos infinito

En este caso, no hay un caso base para detener la recursión, por lo que la función seguirá llamándose a sí misma con un valor más pequeño de $n$, llevando a una recursión infinita.

Cómo Evitar la Recursión Infinita:

• Para evitar la recursión infinita, es crucial asegurarse de que cada función recursiva tenga un caso base adecuado.

• El caso base debe representar una condición bajo la cual la función deja de hacer llamadas recursivas y devuelve un resultado.

• Al escribir una función recursiva, siempre pregúntate: "¿Qué condición debe hacer que la función se detenga y devuelva un resultado?"

• Asegúrate de que el caso base sea alcanzable y que las llamadas recursivas conduzcan hacia él.

Ejemplo Corregido:

• Vamos a corregir el ejemplo anterior añadiendo un caso base para detener la recursión cuando $n$ llegue a $0$:

def cuentaRegresiva(n):
  # Caso base
  if n == 0: return
  # Imprimir el número actual
  print(n)
  # Llamar a la función cuentaRegresiva con el siguiente número más pequeño
  cuentaRegresiva(n - 1)

# Ejemplo de uso:
cuentaRegresiva(5)  # Imprime números del 5 al 1

• Ahora, la función dejará de llamarse a sí misma cuando $n$ se convierta en $0$, evitando la recursión infinita.

En resumen, la recursión infinita ocurre cuando una función recursiva se llama a sí misma indefinidamente sin alcanzar un caso base. Para evitarla, asegúrate siempre de que tus funciones recursivas tengan un caso base adecuado que detenga la recursión y devuelva un resultado. Probar tus funciones recursivas con diferentes valores de entrada puede ayudar a detectar posibles casos de recursión infinita durante el desarrollo.

Implementando Algoritmos Recursivos

Presenta una serie de problemas de programación adecuados para la recursión

Vamos a discutir algunos algoritmos recursivos bien conocidos.

Podemos resolver el problema usando un algoritmo de complejidad $O(n)$. Podemos escribir un bucle for simple:

# Leer los datos de entrada
x, n, m = map(int,input().split())

# Inicializa una variable res a 1.
# Esta variable almacenará el resultado de x^n mod m
res = 1

# calcular el valor x^n mod m usando n multiplicaciones 
# 1 * x * x * ... * x
for i in range(1,n+1):
  res = (res * x) % m

# imprime la respuesta
print(res)

Este programa excede el límite de tiempo. Dado que $n\le 10^9$, y el límite de tiempo para este problema es de solo $1$ segundo, no se pueden realizar $10^9$ operaciones en $1$ segundo incluso utilizando computadoras modernas.

¿Cómo podemos acelerar el proceso de multiplicación? Por ejemplo, si queremos calcular $x^{100}$, podemos descomponerlo en $(x^2{)}^{50}$. Utilizando solo una multiplicación para calcular $x^2$, podemos reducir efectivamente la potencia a la mitad: de $100$ a $50$.

Por ejemplo, en lugar de utilizar $16$ multiplicaciones para encontrar $x^{16}$, podemos reescribir la expresión de la siguiente manera: $x^{16}=(((x^2{)}^2{)}^2{)}^2$, realizando así solo $4$ multiplicaciones. De manera similar, podemos concluir que para encontrar $x^{1024}$, es suficiente realizar solo $10$ multiplicaciones.

Si el exponente es impar, por ejemplo, $n=99$, calculamos el valor de $x^{99}$ como $x\cdot x^{98}$.

Por ejemplo, $x^{15}=((x^2\cdot x{)}^2\cdot x{)}^2\cdot x$.

Hemos llegado al método de exponenciación binaria, una técnica utilizada para calcular grandes potencias de un número de manera eficiente. Se basa en el principio de que cualquier número elevado a una potencia puede expresarse como una secuencia de potencias de $2$.

Dado un número base $x$ y un exponente $n$, expresamos $n$ como una suma de potencias de $2$. Por ejemplo, si $n=13$, podemos escribirlo como $13=8+4+1$. Luego, calculamos $x^n$ multiplicando juntos $x$ elevado a cada potencia de $2$ y combinando los resultados.

Supongamos que queremos calcular $x^{13}$.

• Expresar $13$ en binario: $13=1101$ en representación binaria.

• Luego, calcular $x^1$, $x^4$ y $x^8$ (correspondientes a los bits establecidos en la representación binaria de $13$).

• Finalmente, multiplicar estos valores juntos: $x^{13}=x^1\cdot x^4\cdot x^8$.

Ventajas. La exponenciación binaria reduce el número de multiplicaciones necesarias en comparación con la exponenciación ingenua. Es particularmente eficiente para exponentes grandes, ya que requiere solo $O(lo{g}_{2}n)$ multiplicaciones en lugar de $O(n)$ multiplicaciones.

Para encontrar el valor de $x^{n}modm$, utilizaremos la fórmula:

# La función myPow encuentra el valor de x^n mod m
def myPow(x, n, m):
  if (n == 0): return 1
  if (n % 2 == 0): return myPow((x * x) % m, n / 2, m)
  return (x * myPow(x, n - 1, m)) % m

# La parte principal del programa. Leer los datos de entrada
x, n, m = map(int, input().split())

# Calcular e imprimir la respuesta
print(myPow(x, n, m))

Python tiene una función incorporada $pow(x,n,m)$, que calcula $x^{n}modm$. El código anterior puede reescribirse de la siguiente manera:

# Leer los datos de entrada
x, n, m = map(int, input().split())

# Calcular e imprimir la respuesta
print(pow(x, n, m))

El Máximo Común Divisor (MCD) de dos números enteros $a$ y $b$ es el mayor número entero positivo que divide tanto a $a$ como a $b$ sin dejar residuo.

Ejemplo:

• Tomemos dos números enteros, $a=12$ y $b=18$.

• Los divisores de $12$ son $1,2,3,4,6$, y $12$.

• Los divisores de $18$ son $1,2,3,6,9$, y $18$.

• Los divisores comunes de $12$ y $18$ son $1,2,3$, y $6$.

• De estos divisores comunes, el mayor es $6$.

• Por lo tanto, $mcd(12,18)=6$.

Propiedades:

• El MCD siempre es un número entero positivo.

• Si $a$ y $b$ son ambos cero, entonces $mcd(a,b)=0$.

• Si $a$ o $b$ (o ambos) son negativos, entonces $mcd(a,b)$ es el mismo que el MCD de sus valores absolutos.

• Si $a$ o $b$ es cero, entonces $mcd(a,b)$ es el valor absoluto del número no cero.

• El MCD de cualquier número y $0$ es el valor absoluto del número en sí.

Aplicaciones:

• El MCD se utiliza en varios cálculos matemáticos, incluyendo la simplificación de fracciones y la búsqueda del denominador común más pequeño.

• Se utiliza en algoritmos criptográficos, como RSA, para la generación de claves y la encriptación.

• También se utiliza en algoritmos de ciencias de la computación, como el algoritmo de Euclides para encontrar el MCD de dos números de manera eficiente.

El algoritmo de Euclides es un método eficiente para encontrar el MCD de dos números enteros. Se basa en el principio de que el MCD de dos números permanece igual si restamos el número más pequeño del número más grande hasta que uno de ellos se convierte en cero.

Si en lugar de la operación "menos" utilizamos la operación "módulo", los cálculos serán más rápidos.

Por ejemplo, para encontrar el $MCD(1,10^9)$ utilizando la resta, se deben realizar $10^9$ operaciones. Sin embargo, al utilizar la operación de módulo, solo es suficiente una acción.

Dado dos números enteros $a$ y $b$, donde $a\ge b$, realizamos repetidamente los siguientes pasos:

• Si $b$ es cero, el MCD es $a$.

• De lo contrario, reemplazamos $a$ con $b$ y $b$ con el residuo cuando $a$ se divide por $b$. Esto puede expresarse como $a\leftarrow b$ y $b\leftarrow amodb$.

• Continuamos este proceso hasta que $b$ se convierte en cero.

El MCD de $a$ y $b$ es el valor de $a$ cuando $b$ se convierte en cero.

El algoritmo de Euclides es eficiente, con una complejidad de tiempo de $O(lo{g}_{2}min(a,b))$. Está garantizado que termina ya que el valor de $b$ disminuye con cada iteración, y eventualmente, $b$ se convierte en cero.

El MCD de dos números puede encontrarse usando la fórmula:

def mcd(a, b):
  if a == 0: return b
  if b == 0: return a
  if a > b: return mcd(a % b, b)
  return mcd(a, b % a)

# La parte principal del programa. Leer los datos de entrada. 
a, b = map(int, input().split())

# Encontrar e imprimir el MCD de dos números.
print(mcd(a, b))

La fórmula dada puede expresarse de otra forma:

def mcd(a, b):
  if b == 0: return a
  return mcd(b, a % b)

# La parte principal del programa. Leer los datos de entrada.
a, b = map(int, input().split())

# Encontrar e imprimir el MCD de dos números.
print(mcd(a, b))

Python tiene una función incorporada $gcd(a,b)$ que calcula el Máximo Común Divisor de dos números. El código anterior puede reescribirse de la siguiente manera:

import math

# Leer los datos de entrada.
a, b = map(int, input().split())

# Encontrar e imprimir el MCD de dos números.
print(math.gcd(a, b))

Lista de problemas

Programas recursivos:

• 1603. La suma de los dígitos

• 1658. Factorial (utilizado en la lección)

• 2999. Función – 10

• 8609. Recursión – 1

• 11249. Recursión – 2

Números de Fibonacci:

• 3258. Secuencia de Fibonacci (utilizado en la lección)

• 8295. Generación de cadena de Fibonacci

MCD / MCM:

• 136. El segmento

• 1601. MCD de dos números (utilizado en la lección)

• 1602. MCM de dos enteros

• 2214. Función 9

• 7363. Suma de fracciones

Coeficiente binomial:

• 3260. ¿Cuántos?

Exponenciación:

• 273. Exponenciación modular

• 5198. Exponenciación modular (utilizado en la lección)

• 9644. Suma de potencias

• 9646. Suma de potencias 2