HOWTO · Python
Multiplicación recursiva en Python
usa la recursividad para multiplicar dos enteros en Python
En esta página
Python ya multiplica enteros con *, pero escribir la multiplicación de forma recursiva es una manera útil de ver cómo un problema puede reducirse a versiones más pequeñas de sí mismo. Los ejemplos siguientes presentan la suma repetida, una estrategia de división por mitades y una variante con acumulador. Sirven para aprender; en el código habitual de una aplicación, usa el operador integrado.
Cómo funciona la recursividad
Una función recursiva resuelve un problema llamándose a sí misma con una entrada más pequeña. Necesita un caso base que devuelva un resultado sin realizar otra llamada y un caso recursivo que avance hacia ese caso base. Cada llamada espera a que regrese la llamada que inició; después, las operaciones pendientes terminan a medida que se deshacen las llamadas.
En la multiplicación mediante suma repetida, el caso recursivo reduce el multiplicador en uno y suma el multiplicando al resultado devuelto. Se llega al caso base cuando el multiplicador es cero. Sin una condición que detenga las llamadas, la función no puede producir un resultado.
Multiplicación recursiva básica
La versión más sencilla reduce la segunda entrada en uno en cada llamada y luego suma la primera entrada a medida que regresan las llamadas.
Ejecuta este ejemplo:
El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.
def recursive_multiply(a, b):
if b == 0:
return 0
if b < 0:
return recursive_multiply(-a, -b)
return a + recursive_multiply(a, b - 1)
print(recursive_multiply(5, 3))
La función suma a una vez por cada unidad positiva de b. Cuando b es negativo, cambiar el signo de ambos operandos permite usar la misma recurrencia de conteo positivo y conservar el producto; esto también permite usar multiplicandos negativos.
Cada llamada reduce b en uno hasta llegar al caso base. Después, las llamadas regresan en orden inverso y suman a en cada paso. Así es fácil seguir la recurrencia, pero la cantidad de llamadas es proporcional al valor absoluto del multiplicador. Por tanto, un multiplicador grande puede superar el límite de recursividad de Python.
Cómo manejar enteros negativos y cero
La misma función maneja el cero y todas las combinaciones de signos. Si el multiplicador es cero, devuelve cero de inmediato. Si el multiplicador es negativo, cambiar el signo de ambos operandos convierte el cálculo en el caso de multiplicador positivo y conserva el producto matemático.
El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.
def recursive_multiply(a, b):
if b == 0:
return 0
if b < 0:
return recursive_multiply(-a, -b)
return a + recursive_multiply(a, b - 1)
for pair in ((5, 3), (-5, 3), (5, -3), (-5, -3), (5, 0)):
print(pair, recursive_multiply(*pair))
Los cuatro casos con signo producen los resultados según la regla habitual: los operandos con el mismo signo dan un resultado positivo y los que tienen signos distintos dan uno negativo. Si uno de los operandos es cero, el resultado es cero. El bucle imprime cada par de entradas junto a su producto, lo que facilita comparar cómo afectan los signos.
Reducir las llamadas recursivas dividiendo por mitades
No hace falta restar uno repetidamente cuando se puede dividir el multiplicador por la mitad. Para un valor positivo de b, sea half el producto de a y b // 2. Si b es par, el resultado completo es half + half; si es impar, hay que sumar una vez más a. La división entera y la comprobación del resto expresan esta recurrencia sin operaciones bit a bit.
El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.
def multiply_by_halving(a, b):
if b == 0:
return 0
if b < 0:
return multiply_by_halving(-a, -b)
half = multiply_by_halving(a, b // 2)
if b % 2 == 0:
return half + half
return half + half + a
print(multiply_by_halving(5, 3))
En cada paso recursivo, el multiplicador se reduce aproximadamente a la mitad; por eso, la profundidad de las llamadas crece en proporción al número de veces que se puede dividir el multiplicador por dos, no a su magnitud. El método sigue realizando sumas y usando la pila de llamadas de Python. Es una forma útil de ilustrar cómo reducir una recurrencia, aunque para el código habitual la multiplicación integrada es más sencilla.
Recursividad de cola en Python
En una función recursiva de cola, la llamada recursiva es la última operación; un acumulador transporta el resultado durante las llamadas. Esto cambia dónde se registra el trabajo pendiente, pero Python no optimiza las llamadas de cola reutilizando un único marco de pila. Por tanto, la limitación de la pila de llamadas sigue presente.
El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.
def tail_recursive_multiply(a, b, accumulator=0):
if b == 0:
return accumulator
if b < 0:
return tail_recursive_multiply(-a, -b, accumulator)
return tail_recursive_multiply(a, b - 1, accumulator + a)
print(tail_recursive_multiply(5, 3))
El acumulador empieza en cero y suma una unidad de a en cada paso positivo. Cuando el multiplicador llega a cero, contiene el producto. Al igual que la suma repetida, esta versión realiza una cantidad lineal de llamadas respecto a la magnitud del multiplicador, así que el estilo de llamada de cola no hace que las entradas grandes sean seguras en Python.
Cuándo resulta útil la multiplicación recursiva
Estas implementaciones aclaran los casos base, el avance recursivo y la diferencia entre una profundidad de llamadas lineal y una logarítmica. La suma repetida y la versión recursiva de cola tienen una profundidad lineal; la versión que divide por mitades tiene una profundidad logarítmica. Todas siguen teniendo el coste de las llamadas a funciones y de la pila, y Python no garantiza un límite fijo de profundidad recursiva válido en todos los entornos.
Para la aritmética práctica con enteros, es preferible usar a * b: resulta más claro y evita las llamadas recursivas adicionales a nivel de Python. Usa la multiplicación recursiva para estudiar la recursividad o cuando el problema requiera específicamente una formulación recursiva, y mantén las entradas lo bastante pequeñas para la recurrencia elegida.