Recursión

Javier Blanco

Recién iniciado el siglo XIII, Leonardo de Pisa, hijo de Bonacci y conocido luego
como Fibonacci (apócope de filius Bonacci), publicó su libro de cálculo, Liber Abaci.
En este libro presentó una secuencia que describía, entre otras cosas, la progenie
de sucesivas generaciones a partir de una pareja de conejos. La secuencia era
conocida desde antes, sobre todo en India, pero quedó bautizada como secuencia
de Fibonacci:
0 , 1,1,2,3,5,8,13,21,34,55,89,144 , …
En esta secuencia, luego de los dos primeros valores dados arbitrariamente, cada
valor es igual a la suma de los dos anteriores.
Si consideramos la secuencia como una función (puede pensarse que el valor
de entrada es el número de generación, y el resultado la cantidad de conejos),
puede expresarse de manera recursiva (con dos casos base) de la siguiente
manera:
fib(0)=0 fib(1)=1 fib( n+2)=fib (n)+ fib(n+1)
Esta definición puede leerse como dos casos elementales (0 y 1) y luego una
definición aparentemente circular, donde para números mayores o iguales a 2 (n +
2) se define como la suma de la misma función aplicada a los dos valores
anteriores. La recursión es esta forma de definición de funciones, donde el valor
para un número natural dado se calcula a partir de los valores de la función para los
números más chicos. No entraremos aquí en cuestiones técnicas acerca de cuándo
está bien definida una función recursiva, pero en general puede decirse que las
funciones recursivas se definen en términos de versiones más simples de sí
mismas.
La idea de recursión como forma de definición de funciones estuvo asociada
desde su tardío inicio en el siglo XIX a los números naturales y al principio de
demostración por inducción matemática completa o fuerte. Si bien algunos
matemáticos clásicos, incluido Euclides, usaron ideas inductivas o recursivas, su
naturaleza sintáctica solo cobró forma cuando se empezaron a considerar los
fundamentos de la matemática, y cobró vuelo con la aparición de la meta-
matemática desarrollada, entre otros, por David Hilbert y Kurt Gödel. Cuando en
1934 Gödel propuso la noción de función recursiva general, su expectativa era que
incluyera a todas las funciones que podían ser computadas o calculadas usando un
procedimiento finito.
Un ejemplo más sofisticado, muestra de manera más elocuente en qué
sentido las definiciones recursivas pueden ser vistas como una manera de describir
de manera finita un número infinito de valores, incluso cuando esos valores son
funciones. Consideremos la función f2 que eleva al cuadrado el número que recibe
como argumento (usamos el punto para expresar la multiplicación de números):
f 2 (n)=n . n
La función que eleva al cubo, la podemos llamar f3, puede definirse, usando la
función anterior, como
f 3 (n)=n . f 2( n)
de manera análoga, puede definirse la función que eleva a la potencia cuarta
f 4 (n)=n . f 3 (n)
y así sucesivamente. El proceso es claramente repetitivo (o recursivo). En lugar de
tener que hacer un imposible número infinito de definiciones (una función para cada
valor al cual se eleva a n), podemos hacer una sola función recursiva que toma dos
valores, el primero de los cuales será el exponente al cual se va a elevar al otro
valor. Al igual que en el caso de la sucesión de Fibonacci, habra casos elementales
(en este caso sólo uno) y casos recursivos. Recordemos que elevar a la potencia 0
da como resultado 1, lo que tomamos como nuestro caso base en la siguiente
definición:
( i ) f (0 , n)=1
( ii ) f ( m+1 , n)=n . f (m, n)
En lugar de tener ahora infinitas funciones, tenemos solo una, y puede recuperarse
cualquiera de las anteriores usando un valor particular para el primer argumento, por
ejemplo
f 3 (n)=f (3 , n)
Una de las propiedades de las funciones recursivas, es que pueden ser
evaluadas mecánicamente, paso a paso. Por ejemplo, si se quiere elevar el número
2 a la potencia quinta aplicando la definición anterior, se puede partir de la expresión
f(5,2) e ir reemplazando paso a paso de acuerdo a las ecuaciones dadas. Para
empezar, se puede ver que 5 = 4 + 1 (lo cual lo deja ya en el formato de la segunda
ecuación). Mostramos los pasos sucesivos de reducción, en los que puede notarse
la característica mecánica de su aplicación, entre llaves {} ponemos la justificación
elemental del paso en esa línea:
f (5,2)=f ( 4+ 1,2){5=4+ 1}
¿ 2. f ( 4,2){ecuaci ó n(ii)}
¿ 2. f (3+ 1,2) {4=3+1}
¿ 2.(2. f (3,2)){ecuaci ó n(ii) }
¿ 2.(2. f ( 2+ 1,2)){3=2+1 }
¿ 2.(2.(2. f (2,2))) {ecuaci ó n(ii)}
¿ 2.(2.2 . f (1+1,2)){2=1+ 1}
¿ 2.(2.(2.(2. f (1,2)))) {ecuaci ó n(ii)}
¿ 2.(2.(2.(2. f (0+1,2)))){1=0+1 }
¿ 2.(2.(2.(2.( 2. f (0,2))))){ecuaci ó n (ii)}
¿ 2.(2.(2.(2.( 2.1)))){ecuaci ó n (i)}
¿ 32 {aritm é tica }
El último paso es en realidad una secuencia de multiplicaciones de adentro hacia
afuera. De aquí viene el origen de la palabra recursión: re-cursar, volver sobre el
curso o correr hacia atrás (del latín recursionem, que a su vez deriva de recurrere).
Vamos a considerar a continuación algunos conceptos relacionados con el de
recursión y que muchas veces quedan subsumidos en este. En primer lugar, la idea
de iteración estará íntimamente relacionada con la de recursión. Por iteración se
entiende la repetición de un proceso para obtener un resultado. La cantidad de
pasos de repetición puede ser un número fijo dado de antemano, o puede continuar
hasta que el estado del proceso satisfaga alguna condición. Recursión e iteración
son inter-definibles: la iteración es equivalente a un caso particular de recursión
llamado recursión final (en inglés tail-recursion) mientras que toda recursión puede
ser implementada por dos iteraciones (manteniendo en el estado una lista de las
llamadas recursivas a resolver). En el ejemplo de la evaluación de f que dimos, la
primera iteración es la que va reduciendo el primer parámetro de f hasta llegar a
eliminar de las expresiones el nombre “f” mismo, mientras que la segunda iteración
queda implícita y es el recorrido hacia atrás para resolver todas las multiplicaciones.
Un uso metafórico e incluso gráfico de la idea de recursión está asociada al
hoy llamado efecto Droste, a partir de una marca de cacao holandesa de inicios del
siglo XX. La imagen en el paquete era una persona que sostenía una bandeja con
una taza de cacao y el paquete mismo en el cual estaba, por supuesto, la imagen en
la cual había una persona sosteniendo una taza y el paquete en el cual… y así
sucesivamente hasta el infinito. Una versión local de la misma idea es la lata de
polvo de hornear Royal. No hay aquí una idea bien definida de recursión, ya que no
se llega nunca a un caso base, y la noción correcta es la de co-recursión.
Las funciones co-recursivas se usan para generar o transformar objetos
complejos, usualmente infinitos. La presentación de la co-recursión se realiza con
ecuaciones análogas a la recursión, pero, entre otras diferencias, no es necesario
un caso base. Por ejemplo, pueden definirse sucesiones infinitas de números,
usualmente llamadas “streams” en inglés y construirlas o definir operaciones sobre
ellas usando co-recursión.
Consideremos la operación cons que agrega un elemento a una sucesión
(escrita aquí entre corchetes). Por ejemplo cons(3, [1, 2]) = [3,1,2]. La sucesión a la
que se agrega el elemento puede ser finita o infinita. Podemos construir entonces
co-recursivamente la sucesión infinita de todos los números naturales (empezando
en 0) llamada nat como sigue, haciendo uso del generador gen, que funciona como
si fuera un índice temporario, y del constructor cons:
nat=gen(0) gen(n)=cons(n , gen(n+ 1))
Si ahora uno quisiera evaluar el valor de nat, definido como gen(0), tendría que
evaluar gen(1), y ésta a su vez gen(2), y así infinitamente. Podrían calcularse tantos
pasos como se quiera, por ejemplo:
gen ( 0 )=cons ( 0 , gen ( 1 ) ) =cons ( 0 , cons ( 1 , gen ( 2 ) ) ) =…
…=[0,1,2,3,4,5 , ...]
Como se ve, esta secuencia de pasos puede seguir hasta el infinito.
Justamente en ese inalcanzable límite tendríamos una secuencia infinita de
naturales. Pese a su constitución casi paradojal, puede postularse la existencia de
funciones co-recursivas e incluso usarse de manera muy útil en contextos de
programación, donde originalmente solía ser llamada “programación circular”.
Como vimos, la recursión es un mecanismo de definición de funciones sobre
los números naturales que puede extenderse a otros dominios, usualmente aquellos
donde sus elementos se definen constructivamente (por ejemplo, palabras, listas de
elementos, árboles, expresiones en algún lenguaje formal, etc.). Las definiciones
recursivas dan lugar a formas mecánicas de evaluar el valor de la función para
alguna entrada dada, lo cual las ha vuelto un concepto importante en diversos
lenguajes de programación. También pueden funcionar como modelo descriptivo de
diversos fenómenos, como es el caso de la sucesión de Fibonacci, y como potente
herramienta de trabajo en matemática y ciencias exactas.
En tanto forma constructiva de definir funciones, la recursión es una manera
precisa y efectiva de lidiar con ciertos objetos infinitos. Como se vio en el ejemplo de
las potencias de números, un número infinito de funciones de un argumento puede
ser compactado en una sola función de dos argumentos. La recursión es una de las
formas más simples y precisas de inscribir en la finitud una importante (y claramente
infinita) colección de entidades infinitas.
Como es usual en matemática, se requieren criterios de buena definición
(existencia y unicidad) de las funciones definidas recursivamente. En los ejemplos
precedentes, mostramos cómo la recursión proporciona un método de cálculo
mecánico del valor de las funciones. Dicho método no garantiza a priori la existencia
o la unicidad de una función definida recursivamente, pero provee una semántica
operacional para las que cumplen esas propiedades. En la versión original de las
funciones recursivas generales de Herbrand-Gödel, se postulaban reglas de cálculo
análogas a las usadas aquí, y se requería una demostración de su buena definición
en un marco lógico-formal dado.
Para evitar estas complejidades, pero también para realizar efectivamente las
funciones recursivas, tanto conceptualmente como en sistemas computacionales, se
han usado diferentes ideas. Una noción útil para implementar funciones recursivas
es la de reflexividad, que consiste en la posibilidad de que un programa dado (o una
definición de una función) pueda acceder a su propio código. Las máquinas de
Turing no admitían recursión entre sus construcciones primitivas, pero la máquina
universal permite construir programas reflexivos y por lo tanto implementar
funciones recursivas.
Hay reflexividad en un dominio de objetos que tienen un significado activo, es
decir producen determinadas acciones en un contexto dado. Entre los ejemplos de
dominios podemos considerar, como en este caso, programas en ejecución en un
sistema computacional, pero también proteínas en un organismo vivo cumpliendo
funciones específicas, oraciones en el lenguaje, teoremas en matemática.
La reflexividad se basa en dos nociones: codificación e interacción. Por
codificación se entiende que para cada objeto del dominio hay otro objeto (no
necesariamente único) que será considerado como el código de éste, su
representación. La acción del primer objeto, puede ser reconstruida exactamente a
partir de una interacción específica con el objeto que lo codifica, en un proceso que
se llamará de decodificación. Un código C de un objeto O no posee el significado
activo de O, solo lo produce a partir de la decodificación. Ahora, el proceso reflexivo
se dará a partir de la interacción entre un objeto con su propio código, lo cual
permite, entre otras acciones, que un objeto modifique su propio código produciendo
un nuevo objeto con un comportamiento modificado. Nótese que códigos (o
programas) y datos coexisten en el mismo nivel ontológico.
Cuando se habla de recursividad en contextos extra-matemáticos o
computacionales, suele referirse indistintamente a alguno de todos estos conceptos
asociados. A veces podría reducirse al caso particular de la iteración, otras, sobre
todo cuando se resaltan las propiedades paradojales de la recursividad en realidad
suele referirse a funciones co-recursivas, y en muchos casos es la reflexividad la
que aparece en primer plano, como por ejemplo en esta interesante caracterización
conceptual que hace Yuk Hui para distinguirla de la iteración:
La recursividad no es la mera repetición mecánica; se caracteriza por el
movimiento en bucle que vuelve sobre sí mismo para determinarse a sí
mismo, mientras quee todo movimiento está abierto a la contingencia, lo
que a la vez determina su singularidad (Hui, 2019, §1)
Es sobre todo a la reflexividad o a la implementación reflexiva de la recursión que
esta caracterización se aplica. Puede considerarse a la recursividad y a la
reflexividad como las características novedosas que definirían al pensamiento
cibernético del siglo XXI. Este pensamiento es una de las vías para comprender las
drásticas y aceleradas transformaciones que las mediaciones digitales producen en
los procesos de subjetivación, reconfigurando la misma forma material de los
lenguajes, humanos o no, y su agencia.
Dice Paolo Virno:
El regreso al infinito es un fenómeno solo lingüístico, aunque todavía en
condiciones de exhibir la juntura entre lenguaje y pulsiones. Es una compleja
construcción simbólica, que aun así da cuenta del modo en que el ámbito
simbólico (recursividad sintáctica) retroactúa sobre el ámbito subsimbólico
(compulsión de repetición). (Virno, 2013, p. 57)
Véase también: código, computación, efectividad, patrón, programa, recursión.

Referencias y sugerencias
Adams, R. (2011). An Early History of Recursive Functions and Computability: From
Gödel to Turing. Docent Press.
Hofstadter, D. R. (2007) [1979]. Gödel, Escher, Bach: Un eterno y grácil bucle.
Tusquets.
Hui, Y. (2019). Recursivity and contingency. Rowman & Littlefield International Ltd.
Virno, P. (2013). Y así sucesivamente, al infinito: Lógica y antropología. Fondo de
Cultura Económica.
Rogers, H. (1967). Theory of Recursive Functions and Effective Computability.
McGraw-Hill.