Learn Functional Programming with Elixir/

...

/

Unbounded Recursion

Unbounded Recursion

Understand the challenges of unbounded recursion and learn how to tackle them.

We'll cover the following...

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.

We’re not necessarily reducing the problem with each step, and we can’t predict how many steps will be required to finish. A similar problem occurs when we try to use software to map a machine’s file system, even if it’s a more controlled environment than the web. Each directory it finds can have many more directories inside. Let’s explore this type of recursion by creating a program that prints and navigates through a given system directory. Let’s first create a module called Navigator:

defmodule Navigator do 
    def navigate(dir) do
        expanded_dir = Path.expand(dir)
        go_through([expanded_dir])
    end

    defp go_through([]), do: nil
    defp go_through([content | rest]) do
        print_and_navigate(content, File.dir?(content))
        go_through(rest)
    end

    defp print_and_navigate(_dir, false), do: nil 
    defp print_and_navigate(dir, true) do
        IO.puts dir
        children_dirs = File.ls!(dir)
        go_through(expand_dirs(children_dirs, dir))
    end
    
    defp expand_dirs([], _relative_to), do: [] 
    defp expand_dirs([dir | dirs], relative_to) do expanded_dir = Path.expand(dir, relative_to)
        [expanded_dir | expand_dirs(dirs, relative_to)]
    end 
end

The function navigate is our entry point. For example, we can pass .., which Path.expand/1 will transform into a complete path. Then we call the go_through helper, passing the directory in a list. Let’s ...