School of Computing

Evolving recursive programs using non-recursive scaffolding

Alberto Moraglio, Fernando E.B. Otero, Colin G. Johnson, Simon Thompson, and Alex A. Freitas

In Proceedings of the 2012 IEEE World Congress on Computational Intelligence, pages 1596-1603, June 2012.


Genetic programming has proven capable of evolving solutions to a wide variety of problems. However, the successes have largely been with programs without iteration or recursion; evolving recursive programs has turned out to be particularly challenging. The main obstacle to evolving recursive programs seems to be that they are particularly fragile to the application of search operators: a small change in a correct recursive program generally produces a completely wrong program. In this paper, we present a simple and general method that allows us to pass back and forth from a recursive program to an associated non-recursive program. Finding a recursive program can be reduced to evolving non-recursive programs followed by converting the optimum non-recursive program found to the associated optimum recursive program. This avoids the fragility problem above, as evolution does not search the space of recursive programs. We present promising experimental results on a test-bed of recursive problems.

Download publication 1977 kbytes (PDF)

Bibtex Record

author = {Alberto Moraglio and Fernando E.B. Otero and Colin G. Johnson and Simon Thompson and Alex A. Freitas},
title = {Evolving Recursive Programs using Non-recursive Scaffolding},
month = {June},
year = {2012},
pages = {1596--1603},
keywords = {Genetic Programming; Evolutionary Algorithms; Recursion},
note = {},
doi = {},
url = {},
    publication_type = {inproceedings},
    submission_id = {11503_1339378919},
    booktitle = {Proceedings of the 2012 IEEE World Congress on Computational Intelligence},
    refereed = {Yes},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014