Page 42 - revista 2019

Revista de la Facultad de Ingeniería, Año 6, Número 1
¿Qué es la recursividad?

Si queremos una definición de recursividad (o “recursión”, según la Real Academia)
probablemente optemos por alguna de las siguientes posibilidades.

 Una función se llama a sí misma, una y otra vez, hasta que deja de llamarse.
 Una alternativa a iteraciones
 Algo matemático… ¿¡mejor ni meterse!?
 Una forma de reducir complejidad en el diseño de algoritmos
La noción de que es una función que se llama hasta dejar de llamarse es básicamente
correcta: que la función se llame a sí misma identifica la recursividad, y si la función
no dejara eventualmente de llamarse, estaríamos en un ciclo eterno. Los casos en que
la función no se llama a sí misma son clave; volveremos a estos “casos base” más
adelante.

La segunda idea proviene de la teoría de la computación, donde se demuestra que
todo algoritmo puede implementarse con sólo recursividad, sin “loops” o ciclos:
interesante pero poco práctico.
La orientación matemática es probablemente causada por varias definiciones, usadas
frecuentemente al ilustrar recursividad, aún cuando los ejemplos en sí sean poco
relevantes a la práctica usual de un programador.

 El factorial n! de un número n se define como 0!=0, y n!=n×(n-1)! si n>0.
 La serie de Fibonacci 0, 1, 1, 2, 3, 5, 8, 13… (cuyos valores son usualmente
utilizados en metodologías ágiles para estimar complejidad de historias) se
define como F 0=0, F 1=1, y F n=F n-2+F n-1 para n>1.

Estos ejemplos, aunque válidos, no ayudan mucho al estudiante de recursividad,
quien con justeza podría concluir que no representan la realidad del trabajo de
desarrollo. (El humor de Google, mostrado en la figura 1, en que sugiere una
respuesta recursiva a la consulta sobre recursividad, tampoco ayuda.)

Figura 1: Google bromea cuando se consulta por “recursión” en inglés,
preguntando al usuario si en realidad había querido buscar “recursión”.

La recursividad se aplica en definiciones matemáticas, en estructuras de datos, y en
algoritmos de todo tipo, por lo que no es correcto encasillarla; veamos a cambio
cómo hacer para aprovecharla.

¿Cómo pensar recursivamente?

¿Cómo encontrar una función recursiva que resuelva un problema? Esto es en realidad
sencillo a primera vista: debemos comenzar por asumir que tenemos ya la función
que resuelve el problema… ¡y usarla para resolver el problema!

Esto parece plantear un problema existencial: precisaríamos una máquina del tiempo
para poder saber la solución al problema, y así escribirla.. ¡difícil! Hay que corregir la

41