Futhark, un lenguaje funcional orientado a la computación paralela sobre datos, ha carecido de soporte para funciones recursivas durante casi toda su existencia. La ausencia no respondía a una postura ideológica contra la recursión —el propio compilador contiene definiciones recursivas—, sino a la falta de una solución viable para compilarlas en todos sus backends, incluido el de GPU. Los hilos de una GPU tienen pilas diminutas y la memoria debe estar preasignada, lo que choca con el tamaño dinámico que exige una llamada recursiva.
Los autores explican que Futhark es agnóstico respecto al hardware y no quieren complicar el sistema de tipos solo para vetar la recursión en kernels paralelos. La solución general, necesaria únicamente cuando se compila para GPU, proviene del aplanamiento completo: la recursión se intercambia con el map, de modo que el control recursivo se ejecuta en la CPU mientras la GPU realiza operaciones planas en paralelo. La función recursiva se eleva para operar sobre un array completo y simular una iteración del cálculo antes de la siguiente llamada recursiva, con funciones auxiliares que reparten y recombinean entradas. Aunque correcta, esta estrategia puede resultar muy lenta por el movimiento de datos que implica.
El artículo detalla además los ajustes necesarios en el comprobador de tipos —Hindley-Milner convencional, ahora con recursión monomórfica al estilo de Standard ML— y cómo esa decisión interactúa de forma problemática con los size types cuando una función se define sobre un tipo de tamaño [n]i32 y se llama recursivamente con [n/2]i32, un caso de recursión polimórfica que la monomorfización tradicional no soporta. Los autores concluyen que, aun con el soporte añadido, los programadores de Futhark probablemente seguirán usando bucles en la mayoría de los casos.