Recursión frente a bucles en Python

Una de las herramientas más fundamentales en la programación es un bucle. Si bien hay muchos tipos diferentes de bucles, casi cada tipo de bucle tiene la misma función básica: iterar sobre los datos para analizarlos o manipularlos. La recursividad es otro tipo popular de función y, aunque también puede analizar y manipular secuencias de datos de forma similar a un bucle, la recursividad probablemente se entienda menos en muchos casos y, a menudo, puede ser algo confusa. Casi todas las funciones recursivas se pueden reescribir como bucles y viceversa. Sin embargo, cada tipo de función tiene ventajas y desventajas, y saber cuándo usar una u otra es algo que veremos aquí. En el siguiente post, vamos a intentar responder a las siguientes preguntas:

1. ¿Qué es un bucle For?
2. ¿Qué es la recursividad?
3. ¿Cuál es un ejemplo práctico de cada método?
4. ¿Cuándo se debe usar cada uno de los dos métodos?
5. ¿Qué son las estructuras de datos recursivas?

Comencemos con lo que a menudo parece ser el más simple de los dos métodos, el bucle.

Para bucles

Para flujo de bucle

Un bucle for se usa para iterar sobre una secuencia (es decir, una lista, una tupla, un diccionario, un conjunto o una cadena). Un ciclo for termina cada vez que llega al final de la secuencia de datos.

Imaginemos que queremos sumar todos los números debajo de 5 y obtener el total. Claro, simplemente podríamos sumar 1+2+3+4+5. Pero si lo convertimos en una función, nos permite reutilizar la misma función para sumar números por debajo de 10, o 20, o lo que sea. Podría haber casos en los que necesitaríamos agregar dos valores, sin saber cuáles eran los valores, por lo que podría ser útil tener una función que devuelva la suma de números por debajo de cierto valor.

En este caso, podríamos hacer algo como lo siguiente:

Para que este ciclo funcione, necesitaríamos tener todos los números almacenados como una lista para poder iterar sobre cada elemento y agregarlo al total.

Veamos cómo se vería esto en el código real:

def getTotal(n):total = 0para el número en la lista(rango(n+1)):print numbertotal = total + numberreturn total

imprimir obtenerTotal(5)

Nuestra función comienza tomando un número como parámetro. Aquí, usaremos 5 como nuestro parámetro. Luego, estableceremos nuestro total igual a 0. Finalmente, iteramos sobre una lista de números entre 0 y n+1 . Hacemos n+1 aquí, porque list(range(n)) nos daría los números menores que n, pero sin incluir n, que en este caso sería 0,1,2,3,4. Como queremos incluir 5, usaremos n+1.

Si ejecutamos este código, podemos ver que en cada iteración, tenemos el número que esperamos y nos devuelve el total.

Nuestra salida impresa sería así:

01234515

recursividad

La recursividad ocurre cuando cualquier función se llama a sí misma. Una de las grandes diferencias entre la recursión y el bucle es la forma en que termina una función recursiva. En el ejemplo anterior, un ciclo for finaliza al final de la secuencia sobre la que se repite. Sin embargo, una función recursiva podría continuar indefinidamente ya que no necesariamente tiene una secuencia de datos. En cambio, las funciones recursivas tienen lo que se llama una condición base. Una condición base es aquella que terminará el bucle si se cumple la condición.

Tomemos el ejemplo anterior y reescribámoslo usando recursividad. Visualmente, así es como se vería:

En cada función, la función se llama a sí misma con nuevas entradas o devuelve un valor.

Veamos cómo se vería esto también en el código real:

def getTotal(n, total):print nif n == 0: # condición basereturn totalelse:return getTotal(n-1, (total+(n)))

imprimir obtenerTotal(5, 0)

Aquí, podemos pasar un número inicial y una variable total. Cuando se llama a la función por primera vez, el total es 0 y el número es 5. Verificamos si el número es 0. Si no, llamamos a la función nuevamente... pero esta vez en lugar de llamarla con 0 y 5, llamamos con 5–1 y 0+5, y repita este proceso hasta que el número sea 0, momento en el que devolvemos la variable total, 15.

Cálculo de interés compuesto con recursión y bucle

Como un ejercicio un poco más difícil, determinemos el valor de un préstamo o una inversión con interés compuesto. Para determinar cuál sería este valor, necesitamos 4 cosas:

1. Duración en años
2. Tasa de interés
3. Número de veces compuesto por año
4. Cantidad principal

La fórmula para calcular el interés compuesto es la siguiente:

Sin embargo, esto calcularía la cantidad total a la vez. En cambio, querremos hacerlo en un bucle o con recursividad. En ese caso, nuestra variable de tiempo (nt), en realidad se manejará en iteraciones.

En ambos métodos, usaremos cada uno de estos números como variables, por lo que podemos continuar y declararlos y usar las mismas variables para cada método.

Las variables se podrían definir de esta manera:

duración en años = 10 tasa de interés = 0,06 compuesto por año = 12 monto principal = 4000

— — Cálculo de interés compuesto con bucle

Para facilitar el cálculo en un bucle, lo que haremos será primero obtener el número total de veces que se capitalizará el interés. Si se va a capitalizar mensualmente, como lo hemos establecido en nuestras variables, y el número total de años es 10, entonces el resultado será 120, o 10*12. Ahora, podemos recorrer cada número en ese rango, hacer el cálculo del interés compuesto para cada iteración y agregarlo al monto principal.

Así es como se vería el código:

def interés compuesto(principal, compuesto, duración, tasa):totalCompuesto = duración * compuestopara i en rango(1, (totalCompuesto+1)):principal = principal*(1+(tasa/compuesto))return principal

print (interés compuesto (importe principal, compuesto por año, duración en años, tasa de interés))

La única diferencia entre esto y el ejemplo más simple es que solo estamos haciendo algunos cálculos más en cada iteración. En lugar de una secuencia de 5, en realidad estamos iterando sobre los números del 1 al 120, que representan el número total de veces que se capitalizaría el interés.

Si registramos la salida, deberíamos obtener un valor de:

7277.58693613

— — Cálculo de interés compuesto con recursividad

En el ejemplo anterior, nuestra secuencia de datos es 120, que representa el número de veces que se capitalizará el monto principal. Después de llegar al final de la secuencia, el ciclo terminará. Con la recursividad, podríamos configurarlo de manera similar. Podríamos darle a la función duración total, y básicamente tener dos condiciones:

• Condición 1: La Duración no es 0.

Haz el cálculo del interés compuesto. Agregue el nuevo interés al monto principal. Restar 1 de la duración total. Vuelva a llamar al sub con el nuevo monto principal y la nueva duración.

• Condición 2 (condición base): la duración es 0.

Devolver el monto principal.

En nuestro ejemplo recursivo anterior, comenzamos en 5 y terminamos la función cuando llega a 0.

Aquí, haríamos lo mismo, pero comenzaríamos en 120.

def recursión compuesta(principal, compuesta, duración, tasa, númeroDeRecurrencias):if númeroDeRecurrencias == 0:Duracióntotal = compuesto * duraciónelif númeroDeRecurrencias != 0:Duracióntotal = duraciónif duración == 0:return principalelse:nuevaDuración = DuraciónTotal - 1cantidad = principal*( 1+(tasa/compuesto))retorno compuestoRecursión(cantidad, compuesto, nuevaDuración, tasa, 1)

print (recurrenciacompuesta(cantidadprincipal, capitalizaciónporaño, duraciónenaños, tasa de interés, 0))

Aquí, llamamos a la función nuevamente o devolvemos el monto principal revisado. Cada vez que llamamos a la nueva función, la llamamos, pero pasamos la duración menos 1. Cuando la duración es igual a 0, solo devolvemos la cantidad principal.

Cuándo usar la recursividad

El uso de recursividad o bucles puede depender en gran medida del lenguaje que estemos usando o de lo que pretendamos resolver. Por ejemplo, en JavaScript, el uso de la recursividad puede generar errores de marco de pila cuando se alcanza el límite de la pila antes de que se cumpla la condición base. Si ese es el caso, un bucle puede funcionar mejor.

El ejemplo anterior también nos da un gran ejemplo de cuándo la recursividad puede funcionar mucho mejor que un bucle.

Imaginemos que en lugar de realizar un seguimiento de solo los números, como lo estamos haciendo arriba, también queremos realizar un seguimiento de otros datos en cada intervalo de capitalización. Por ejemplo, es posible que deseemos tener en cuenta cómo los pagos regulares afectarían la vida del préstamo. Podríamos querer terminar el ciclo antes de que termine la secuencia. Si el número total de veces que el interés de un préstamo se capitalizaría es 120, entonces la longitud de nuestra lista es 120. Pero, si el monto del préstamo es 0 después de solo 100 iteraciones, tenemos 20 elementos de lista innecesarios y sin usar colgando en el final de nuestra lista. Para complicar aún más un escenario de bucle, el valor de las variables, como el monto del préstamo, depende del valor del monto del préstamo en la iteración anterior. No es que esto sea particularmente difícil, pero es complicado.

Visualmente, así es como podrían verse estos problemas:

Estructuras de datos recursivas

Ahí es exactamente cuando las estructuras de datos recursivas resultan útiles. Una estructura de datos es recursiva si se puede definir en términos de una versión más pequeña de sí misma. Una lista es un ejemplo de una estructura de datos recursiva.

Por ejemplo, tomemos la siguiente lista:

Ahora, hagamos dos listas más pequeñas de nuestra lista original:

Si imprimiéramos ambas listas, obtendríamos lo siguiente:

La razón por la que esto es tan poderoso es que con funciones recursivas y estructuras de datos recursivas, podemos modificar una lista completa, o una porción más pequeña de una lista más grande, todo a la vez. Cuando estábamos pensando en este problema con los bucles, solo podemos cambiar un valor en un índice a la vez.

Como ejemplo de cómo hacer esto, considere lo siguiente:

si guardamos estas secciones más pequeñas de la lista más grande, podríamos llamar a la misma función (recursión) y enviarle la lista más pequeña (una estructura de datos recursiva).

Echemos un vistazo a cómo podría funcionar esto con nuestro ejemplo anterior de interés compuesto:

def recursiveData(datos):# Condición base (si el monto principal == 0 o si la duración == 0)

 # Else Condition ( recalculate the times compounded, duration & principal amount)

imprimir (datos recursivos (matriz))

Nuestra función consistiría básicamente en una sentencia if else. Si bien podría volverse más complejo si así lo deseamos, probablemente podamos lograr todo lo que queremos hacer aquí. Eventualmente, queremos devolver los datos finales, que tendrán el monto del préstamo y el pago actual en cada intervalo en el que se capitaliza el préstamo.

Nuestra salida de datos podría verse así:

[{'veces compuesto': 0,'duración restante': 10,'tasa de interés': .06,'pago actual': 100,'compuesto por año': 12,'cantidad principal': 4000},{'veces compuesto': 1, 'duración restante': 10, 'tasa de interés': .06, 'pago actual': 100, 'compuesto por año': 12, 'importe principal': 3900}]

Con esto en mente, y también mirando hacia atrás a nuestros ejemplos de listas más pequeñas, así es como probablemente se verá este proceso:

Con cada llamada recursiva, tomaremos el primer elemento de la matriz de la lista. Luego modificaremos los valores de ese elemento y llamaremos a la función nuevamente, pero esta vez pasándole array[:1] y array[1:] como parámetros. Como podemos ver, a la mitad de la lista, deberíamos tener dos listas del mismo tamaño, y al final, habremos transferido y modificado completamente todos los elementos de la primera lista, y los hemos agregado a la segunda lista. A continuación, iremos paso a paso para crear esta función con código real.

paso 1. Crear la matriz

duraciónEnAños = 10compuestoPorAño = 12

matriz = [{'veces compuesto': 0,'duración restante': 10,'tasa de interés': .06,'pago actual': 50,'compuesto por año': 12,'cantidad principal': 4000,'total compuesto': compuestoPorAño*duraciónEnAños}]*(compuestoPorAño*duraciónEnAños)

En este punto, tenemos una matriz de la longitud del número total de veces que se capitalizaría el préstamo. Cada elemento contiene los mismos datos, que cambiaremos recursivamente.

Paso 2. Crea la función y la condición base

def recursiveData(inputArr, outputArr):if len(inputArr) == 0 or inputArr[-1]['cantidad principal'] <= 0:return outputArr

Nuevamente, nuestra condición base cubre los dos escenarios con los que nos gustaría terminar la función. Si hemos llegado al final de la duración ( len(inputArr) == 0 ) o hemos pagado todo el préstamo ( inputArr[-1]['principal amount'] <= 0 ).

Paso 3. Cree la instrucción else y defina las variables actual, inputArray y outputArray

else:actual = inputArr[:1][0]inputArrayLength = len(inputArr[1:])outputArray = outputArr

En este punto, el elemento actual que estamos extrayendo de inputArr es current . Y nuestra matriz de salida también está definida. Si necesitamos acceder a nuestra matriz de entrada más tarde, podemos hacerlo con la variable inputArr .

Paso 4. Si la longitud de la matriz de salida es 0, extraiga el primer elemento de la matriz de entrada (actual) y colóquelo en la salida sin cambiarlo.

if len(outputArray) == 0:outputArray.append(current)return recursiveData(inputArr[1:], outputArray)

Ahora, nuestras dos matrices deberían parecerse al diagrama que vimos arriba, cuando se llama inicialmente a la función recursiva.

paso 5. Si la matriz de salida es mayor que 0, modifique todos los valores de nuestro elemento actual.

else:newTimesCompounded = outputArray[-1]['veces compuesto'] + 1newDurationRemaining = actual['duración restante']if ((outputArray[-1]['times compuesto'] + 1) % 12) == 0:newDurationRemaining = outputArray[-1]['duración restante'] - 1principal = (outputArray[-1]['importe principal'])*(1+(outputArray[-1]['tasa de interés']/outputArray[-1] ['compuesto por año']))pagoactual = actual['pago actual']if pagoactual > principal:pagoactual = principalnuevoImportePrincipal = (principal - pagoactual)nuevoTotalCompuesto = matriz de salida[-1]['total compuesto'] - 1nuevoActual = {' veces compuestas': nuevasVecesCompuestas,'duración restante': nuevaDuraciónRestante,'tasa de interés': actual['tasa de interés'],'pago actual': pagoActual,'compuesto por año': actual['compuesto por año'],'principal cantidad': newPrincipalAmount,'total compuesto': newTotalCompounded}

En este punto, podríamos imprimir nuestra variable newCurrent , que es la variable current modificada, y tendría todos los datos nuevos después de que se haya compuesto y se haya realizado el pago del préstamo. A continuación, necesitaremos agregar esta variable a nuestra matriz de salida.

Paso 6. Agregue la nueva variable actual a la matriz de salida

outputArray.append(newCurrent)

Paso 7. Llame a la función recursiva con los nuevos parámetros

devolver datos recursivos (inputArr, outputArray)

¡Y hemos terminado! Echemos un vistazo a todo el bloque de código en una sola pieza:

duraciónEnAños = 10compuestoPorAño = 12

matriz = [{'veces compuesto': 0,'duración restante': 10,'tasa de interés': .06,'pago actual': 2000,'compuesto por año': 12,'cantidad principal': 4000,'total compuesto': compuestoPorAño*duraciónEnAños}]*(compuestoPorAño*duraciónEnAños)

def recursiveData(inputArr, outputArr):if len(inputArr) == 0 or inputArr[-1]['cantidad principal'] <= 0:return outputArrelse:actual = inputArr[:1][0]inputArrayLength = len(inputArr [1:])outputArray = outputArrif len(outputArray) == 0:outputArray.append(current)return recursiveData(inputArr[1:], outputArray)else:newTimesCompounded = outputArray[-1]['times compounded'] + 1newDurationRemaining = actual['duración restante']if ((outputArray[-1]['times compounded'] + 1) % 12) == 0:newDurationRemaining = outputArray[-1]['duración restante'] - 1principal = (outputArray [-1]['monto principal'])*(1+(outputArray[-1]['interest rate']/outputArray[-1]['compuesto por año']))pagoActual = actual['pago actual' ]if pagoactual > principal:pagoactual = principalnuevoImportePrincipal = (principal - Pagoactual)nuevoTotalCompuesto = matriz de salida[-1]['total compuesto'] - 1nuevoActual = {'veces compuesto': nuevoVecesCompuesto,'duración restante': nuevoDuraciónRemanente,'tasa de interés' : Actual[ 'tasa de interés'],'pago actual': pagoActual,'compuesto por año': actual['compuesto por año'],'importe principal': newPrincipalAmount,'total compuesto': newTotalCompounded}outputArray.append(newCurrent)inputArr = [newCurrent]*inputArrayLengthreturn recursiveData(inputArr, outputArray)

returnData = recursiveData(array, [])for i in returnData:print (i)

Para asegurarnos de que funciona de la manera que queremos, aumentemos el monto de nuestro pago a algo realmente alto, para asegurarnos de que solo se nos devuelva lo que queremos y que se cumpla nuestra condición básica.

Si cambiamos el monto del pago a 2000, deberíamos obtener los siguientes datos cuando se imprima:

{'veces compuesto': 0, 'duración restante': 10, 'tasa de interés': 0,06, 'pago actual': 2000, 'compuesto por año': 12, 'importe principal': 4000, 'total compuesto': 120 }

{'veces compuesto': 1, 'duración restante': 10, 'tasa de interés': 0,06, 'pago actual': 2000, 'compuesto por año': 12, 'importe principal': 2019,9999999999995, 'total compuesto': 119 }

{'veces compuesto': 2, 'duración restante': 10, 'tasa de interés': 0,06, 'pago actual': 2000, 'compuesto por año': 12, 'importe principal': 30,099999999999227, 'total compuesto': 118 }

{'veces compuesto': 3, 'duración restante': 10, 'tasa de interés': 0,06, 'pago actual': 30,25049999999922, 'compuesto por año': 12, 'importe principal': 0,0, 'total compuesto': 117 }

¡Impresionante! Parecía funcionar, y se cumplió la condición base, y devolvió un conjunto de resultados mucho más limpio de lo que hubiéramos obtenido de otra manera.

Piense en lo molesto que sería si usáramos un bucle para hacer esto, y todavía tuviéramos 120 elementos para revisar, la mayoría de los cuales serían inútiles/vacíos.

En resumen

Trabajar con recursividad puede ser desalentador al principio. Pero hay algunos casos en los que puede ser una herramienta increíble si se usa correctamente. Del mismo modo, los bucles también pueden ser una mejor opción, según el escenario. Saber cómo hacer ambas cosas de manera efectiva puede ser una gran herramienta para el cinturón de herramientas del desarrollador y también una excelente manera de impresionar a los empleadores en las entrevistas técnicas.