Recursión y su relación con la iteración
Seguí leyendo
Enterate del próximo post
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Abrir una muñeca rusa revela otra igual, apenas más chica, en su interior. Abrir esa segunda muñeca revela una tercera, y así siguiendo, hasta llegar a una muñeca que ya no tiene ninguna otra adentro: la más chica de todas, la única que se abre y no revela nada más para seguir abriendo. Contar cuántas muñecas tiene el juego completo se puede resolver exactamente de la misma manera en que se abren: contar la muñeca actual, más las que haya en su interior, hasta llegar a la que no tiene ninguna.
El post anterior cerró con una pregunta abierta: una función puede llamar a otra función ya definida, ¿qué pasa cuando esa otra función es ella misma? Eso es la recursión, y la muñeca rusa que no tiene ninguna otra adentro es, en términos de esta serie, un caso base: la versión del problema tan chica que ya no hace falta seguir llamando a nada para resolverla.
Una función es recursiva cuando, en algún punto de su propio cuerpo, se llama a sí misma para resolver una versión más chica del mismo problema. No hace falta ninguna instrucción nueva para esto: llamar a ... con ... para obtener ... (post 3) ya servía para llamar a cualquier algoritmo ya definido, y una función recursiva simplemente lo usa para llamarse a sí misma, en vez de a otra función distinta.
Toda función recursiva necesita, además, un caso base: una condición que, al cumplirse, devuelve un resultado sin volver a llamarse. Sin un caso base, o con uno que ninguna llamada llega a cumplir nunca, la función se llama a sí misma para siempre, igual que un bucle mientras (post 6) cuya condición nunca se vuelve falsa no termina nunca: las dos formas de repetir comparten la misma obligación de terminar en algún momento, la condición de "finito" que el post 1 de esta serie pedía para cualquier algoritmo.
Cada llamada que no es el caso base tiene que acercar el problema hacia una versión más chica de sí mismo -en los ejemplos de este post, un número que se achica en 1 en cada llamada- para llegar tarde o temprano al caso base. Mientras una llamada espera el resultado de la siguiente, queda pendiente sin poder terminar todavía: las llamadas se acumulan de la misma forma en que una pila (post 12) apila elementos, y se resuelven en el orden inverso al que empezaron, igual que una pila desapila siempre por el mismo extremo por el que apiló último.
La relación con la iteración -los bucles del post 6- es que las dos resuelven el mismo tipo de problema, repetir algo una cantidad de veces, por mecanismos distintos: un bucle usa un contador que avanza en cada vuelta, dentro de un mismo cuerpo de pasos que se repite; la recursión no tiene ningún contador visible, sino una función que se llama a sí misma con un dato cada vez más chico, dejando que el caso base decida cuándo detenerse.
El post de bucles (post 6) sumó los primeros números naturales hasta una cantidad dada con un contador que avanzaba en cada vuelta. El mismo resultado se puede obtener sin ningún bucle, llamando a la propia función con una cantidad cada vez más chica.
algoritmo suma_recursiva(cantidad):
si cantidad es igual a 0:
devolver 0
asignar cantidad a anterior
restar 1 a anterior
llamar a suma_recursiva con anterior para obtener parcial
sumar cantidad a parcial
devolver parcialCon cantidad en 4: la función se llama a sí misma con 3, que se llama con 2, que se llama con 1, que se llama con 0. Ahí se cumple el caso base, y esa última llamada devuelve 0 sin llamarse de nuevo. Desde ahí, cada llamada pendiente termina: la de cantidad en 1 recibe ese 0 como parcial, le suma 1 y devuelve 1; la de cantidad en 2 recibe ese 1, le suma 2 y devuelve 3; la de cantidad en 3 recibe ese 3, le suma 3 y devuelve 6; y la llamada original, con cantidad en 4, recibe ese 6, le suma 4 y devuelve 10 -el mismo resultado que ya daba sumar_primeros(4) con un bucle, en el post 6.
El mismo mecanismo sirve para multiplicar, con un caso base distinto: multiplicar por 0 en cada paso dejaría todo en 0 -el mismo problema que ya advertía el post de bucles sobre el valor de arranque de un acumulador-, así que el caso base de un producto devuelve 1, no 0.
algoritmo producto_recursivo(cantidad):
si cantidad es igual a 0:
devolver 1
asignar cantidad a anterior
restar 1 a anterior
llamar a producto_recursivo con anterior para obtener parcial
multiplicar parcial por cantidad
devolver parcialCon cantidad en 4, la cadena de llamadas es la misma -4, 3, 2, 1, 0- y el caso base devuelve 1: 1 × 1 = 1, 2 × 1 = 2, 3 × 2 = 6, y la llamada original, 4 × 6 = 24 -otra vez, el mismo resultado que ya daba producto_primeros(4) con un bucle, en el ejercicio del post 6.
Definir, usando recursión, una función potencia que reciba una base y un exponente -un número entero mayor o igual a 0- y devuelva la base elevada a ese exponente.
Elevar cualquier número a la 0 da 1, sin importar cuál sea la base: ese es el caso base. Para un exponente mayor a 0, pensar qué cuenta conecta potencia(base, exponente) con potencia(base, exponente - 1).
algoritmo potencia(base, exponente):
si exponente es igual a 0:
devolver 1
restar 1 a exponente
llamar a potencia con base y exponente para obtener parcial
multiplicar parcial por base
devolver parcialCon base en 2 y exponente en 4: el exponente baja de a uno -4, 3, 2, 1, 0-, siempre con la misma base, hasta el caso base, que devuelve 1. Desde ahí: 1 × 2 = 2, 2 × 2 = 4, 4 × 2 = 8, y la llamada original, 8 × 2 = 16, que es 2 elevado a la 4. A diferencia de los dos ejemplos anteriores, acá hay dos parámetros, pero solo uno se achica en cada llamada: base se pasa igual en toda la cadena. exponente sí se puede restar directamente, sin copiarlo antes a una variable aparte, porque a diferencia de cantidad en los ejemplos anteriores, no hace falta su valor original después de la llamada recursiva.
Un juego de muñecas rusas tiene una muñeca inicial de un tamaño dado, en centímetros. Cada muñeca sucesiva, hacia adentro, mide 3 centímetros menos que la anterior, hasta llegar a una tan chica que ya no puede tener ninguna otra adentro. Calcular cuántas muñecas tiene el juego completo, conociendo el tamaño de la primera y el tamaño mínimo posible de una muñeca.
Pensar qué tamaño ya no cuenta como una muñeca más, y a qué tamaño le corresponde resolver el mismo problema una vez que la muñeca actual ya se contó.
algoritmo cantidad_munecas(tamano_actual, tamano_minimo):
si tamano_actual es menor a tamano_minimo:
devolver 0
asignar tamano_actual a siguiente
restar 3 a siguiente
llamar a cantidad_munecas con siguiente y tamano_minimo para obtener parcial
sumar 1 a parcial
devolver parcialCon una muñeca inicial de 20 centímetros y un tamaño mínimo de 5: los tamaños probados son 20, 17, 14, 11, 8, 5 y 2. Con 2, ya menor al mínimo, se cumple el caso base y devuelve 0 -esa muñeca no llega a existir-. Desde ahí, cada llamada suma 1 al resultado de la siguiente: 1, 2, 3, 4, 5, y la llamada original, con 20 centímetros, devuelve 6. El juego completo tiene 6 muñecas -20, 17, 14, 11, 8 y 5 centímetros-, la última de las cuales ya no tiene ninguna otra adentro.
Una función recursiva se llama a sí misma para resolver una versión más chica del mismo problema, hasta llegar a un caso base que devuelve un resultado sin llamarse de nuevo. No es una instrucción nueva de la notación -es la misma llamada a un algoritmo que ya existía desde la descomposición-, y resuelve el mismo tipo de problema que un bucle, por un mecanismo distinto: sin contador visible, dejando que el caso base decida cuándo detenerse.
El próximo paso de la serie no agrega ninguna herramienta nueva: es el primer problema real que combina, en un mismo enunciado, varias de las herramientas ya vistas -estructuras, funciones, composición, recursión- sin que ninguna sección diga de antemano cuál corresponde en cada parte.