Unbounded Recursion

Unbounded recursion is when we can’t predict the number of repetitions for a recursive function. For example, it’s hard to predict how many iterations a web crawler that navigates and downloads web pages will have. For each page it browses, it finds new links to crawl. Since we’re not the owners of the pages, we can’t predict how many links each page will have. For every page that the crawler downloads, the number of pages that it needs to crawl may increase. The web crawler also needs to be cautious with pages it has already visited to avoid circular references and infinite recursion.

All these characteristics of the web crawler represent unbounded recursion challenges, and a functional programmer must be prepared to face them. The following image illustrates the nature of data that leads to an unbounded recursion.