Recursively climb an object to find it's full path.

So recursion can be intimidating, I find myself constantly thinking of numbers and base cases, then figuring it all out from there. APIs and nested data makes me happy... It's like a scavenger hunt. Where's this data and how can I find it. So I came across a fun example of originally trying to find a file path. Given a target file and a file structure can you recreate the path as a string. Which I realized could be extremely useful if you have a JSON object and you're trying to find a specific variable. There are some APIs that are just a huge headache sifting through data. Sort of why I am enjoying GraphQL but that's another story.

For the purpose of this walkthrough and my unimaginative process let's use a file tree. I used to get lost in the Rails file tree all the time so I feel like we can recreate that with some embellishment to make it trickier to find where we are going. Here's how we can represent the path as an object.

let rails = {
    '/app': {
        '/channels': {
            '/application': {
                'channel.rb': null,
                'connection.rb': null
            }
        },
        '/controllers': {
            '/concerns': {
                '.keep': null
            },
            'application_controller.rb': null },
        '/jobs': {
            'application_job.rb': null
        }

    },
    '/config': {
        '/environments': {
            'development.rb': null,
            'production.rb': null,
            'test.rb': null
        }
    },
    '/db': {
        'schema.rb': null,
        'seeds.rb': null,
        '/migrate': {
            'create_tables.rb': null,
            'fix_columns.rb': null
        }
    }
}

If we were to just find that our file is in there that's easy just keep going through each directory an once we find it return true... That would look something like this:

function findFile(structure, target) {
    for (let subdir in structure) {
        if (subdir === target || findFile(structure[subdir], target)) {
            return true
        }
    }
    return false
}
console.log(findFile(rails, 'fix_columns.rb'))

That will return true since fix_columns is somewhere in there... but how can we come to that code in the first place?

Think of the simplest file structure given... just one directory, so let's take

folder = {
            'create_tables.rb': null,
            'fix_columns.rb': null
        }

So here we just need to iterate over the keys and check it against our target file

function findFixColumns() {
    for (let key in folder) {
        if (key === 'fix_columns.rb') {
            return true
        }
    }
    return false
}
console.log(findFixColumns())

So going back to our recursive look, how an || statement works is the left side is evaluated before the right, and will return true if just the left is true. So by diving repeatedly deeper on the right side, by the base case will return true if it has exhausted all options. So that leaves us with our simple, hey it's found on a higher level, "I'm true, get me out of here!" solution. How can we go from there into getting the file path now? Well in Javascript a string is considered true.. so in theory we can work on what we just did and compile a string, instead of just returning true. So we can build on that with two different cases in mind, finding the file and then building on folders.

function findFilePath(structure, target) {
    for (let subdir in structure) {
        if (subdir === target) {
            return `/${subdir}`
        }
        let found = findFilePath(structure[subdir], targetFile)
        if (found) {
            return `${subdir}${found}`
        }

    }
    return null
}

So here, our basecase is finding the target file. It will return a string, which will translate to true. If that isn't the top level, we will continue on in our function and search the filepath in the subdirectories, since found is our basecase return we build off of that and apply our subdir which is the directory it is found in... so when we try this for our fix_columns.rb friend, the return would be:
/db/migrate/fix_columns.rb.
Woooo, we've recursively found our file by figuring out the base case and building up.

For me these word problems seem way less stressful than dealing with numbers and fibonacci but that may be my love of puns. Not all recursion is scary. One of my favorite recursive functions for a production app was with the Eventbrite API being very cranky and only giving 50 results at a time when I needed 200... So recursively called and added to an array... such fun times. APIs have so much data that manipulating it into what you want may be stressful, but just think of it as wordplay and you might just enjoy it.