Automatic generation of recursive algorithms for list manipulation

Recursion consists of building algorithms based on your own definition. This article presents recursive algorithms automatically generated via Genetic Programming (PG) with one or more recursive calls for five list manipulation problems, which are interpretable and allow new knowledge to be obtained. The main difficulty that arises in the automatic generation of recursive programs is the handling of the halting problem, which several works have managed to overcome in bounded recursion problems. This work analyses and criticises the implemented techniques and proposes a solution for when explicit recursive algorithms are evolved that solve problems where the elements of a list must be manipulated. Examples of programs evolved in Python 3.6 that contain one or more recursions and whose code is included for verification are presented and analysed. In conclusion, fully functional and interpretable recursive algorithms are generated in all cases. Furthermore, the evolutionary process allows the generation of algorithms with a greater number of recursions, although without a significant contribution to the algorithm during its execution. Finally, it is observed that the challenge to generate this type of algorithm is mainly in the fitness function.