R Recursion - Part 2 | Become Great at R

In the Environments chapter of the book Advanced R, Hadley gives a function where(name, env = parent.frame()) that finds the first environment where a given name is defined. The parameter env is the environment where the search begins. Its default value is the global environment (the environment where we normally work). The function was written recursively. I encourage you to study it first before reading on because I’m giving a solution here to one of the exercises, which asks to write a recursive function to find all environments that contain a binding for name.

Here’s my solution.

where_all = function(name, env = parent.frame()) {
        # Finds all environments that contain a binding for name.
        # 
        # name: string, name of an object
        # env : environment object where the search begins
        
        if (identical(env, emptyenv())) { # base case
                res = NULL
        } else { # non-base case
                if (exists(name, envir = env, inherits = F)) { # success case
                        res = env
                } else { # fail case
                        res = NULL
                }
                        
                # recursive step
                c(res, where_all(name, parent.env(env)))
        }
}

Let’s test it.

# test
mean = function(x) "guck"
where_all("mean")

## [[1]]
## <environment: R_GlobalEnv>
## 
## [[2]]
## <environment: base>

Now inside of where_all() I used a base R function exists() to check if name is in the current environment. But we don’t have to use it, instead, we can implement our own version using recursion. Below is how to do it.

exists2 = function(name, env=parent.frame(), inherits = T) {
        # Checks if name is in the given environment or its parent environments.
        # 
        # name: string, name of an object
        # env : environment object where the search begins
        # inherits: logical

        if (inherits) {
                if (identical(env, emptyenv())) { # base case
                        FALSE
                } else { # non-base case
                        if (name %in% ls(env)) { # success case
                                TRUE
                        } else { # fail case
                                # recursive step
                                exists2(name, parent.env(env)) 
                        }
                }        
        } else {
                name %in% ls(env)
        }
}

We can simplify the code a bit by collapsing the if...else... inside the non-base case with the outside else clause. This makes the code a bit easier to read.

exists2 = function(name, env=parent.frame(), inherits = T) {
        # Checks if name is in the given environment or its parent environments.
        # 
        # name: string, name of an object
        # env : environment object where the search begins
        # inherits: logical
        
        if (inherits) {
                if (identical(env, emptyenv())) { # base case
                        FALSE
                } else if (name %in% ls(env)) { # success case
                        TRUE
                } else { # fail case
                        exists2(name, parent.env(env)) # recursive step
                }
        } else {
                name %in% ls(env)
        }
}

Let’s test it out.

e = new.env()
e$x = 109
e$y = 83
rm("x", envir=e)
exists2("y", env=e)

## [1] TRUE

exists2("y")

## [1] FALSE

exists2("x", env=e)

## [1] FALSE

ls(e)

## [1] "y"

Take a moment to compare exists2() and where_all(). Where does the recursive step happen? In exists2(), it happens when the fail case is triggered. But in where_all(), it happens after both the success and fail cases. So the take away is that although all recursions are the same in concept but they can differ in implementation. The key difference lies in where the recursive step happens.

Categories