How Would I refactor this Depth First Search function to remove mutation

Your attempt needs a few corrections:

• Spelling of s and str is not consistent
• The start parameter needs a default value of 0
• The recursive call is made with a wrong index. Not start + 1, but i
• The base case should not place the whole string in an array. On the contrary that newly pushed array should be empty: result.push([]) or why not return [[]] immediately.
• results.length will never be zero when coming back from recursion; the else block will never execute -- it can be omitted.
• The for loop is making one iteration too few. The end condition should be i <= s.length

Here is the corrected version:

function partition(s, start=0) {
    if (start == s.length) {
        return [[]];
    }
    let result = [];
    for (let i = start + 1; i <= s.length; i++) {
        const prefix = s.slice(start, i);
        if (isPalindrome(prefix)) {
            for (const part of partition(s, i)) {
                result.push([prefix, ...part]);
            }
        }
    }
    return result;
}

Note that this makes the solution a tad slower.

If you appreciate single-exit functions, you might also appreciate a (mutation-free) single-expression version:

const isPalindrome = (s) => s .split ('') .reverse () .join ('') == s

const palindromePartition = (s, i = 1, p = s .slice (0, i)) => 
  s .length == 0
    ? [[]]
  : i > s .length
    ? []
  : [
      ... (isPalindrome (p) ? palindromePartition (s .slice (i)) .map (pp => [p, ...pp]) : []),
      ... (palindromePartition (s, i + 1))
    ]


console .log (palindromePartition ('aab'))
console .log (palindromePartition ('levelalevel'))

.as-console-wrapper {max-height: 100% !important; top: 0}

Here the body of our main function (so too the body of the isPalindrome helper) is a single expression. Developed independently from the original or trincot's refactoring, it mostly still expresses the same logic, just structures it differently.

Here are Trincot's answers modified to be single entry, single exit. For anyone wondering why someone would want to do this, or for the inevitable downvoting it will get by the early return brigade, I've provided an analogy and a diagram at the bottom.

function partition(str, start = 0) {
    const result = [];
    
    if (start != str.length) {
        for (let i = start + 1; i <= str.length; i++) {
            const prefix = str.slice(start, i);
            
            if (isPalindrome(prefix)) {
                const partitions = partition(str, i);
                
                if (partitions.length == 0) {
                    result.push([prefix]);
                } else {
                    for (const part of partitions) {
                        result.push([prefix, ...part]);
                    }
                }              
            }
        }
    }
    
    return result;
}

function partition(str, start = 0) {
    const result = [];
    
    if (start != str.length) {
        for (let i = start + 1; i <= str.length; i++) {
            const prefix = str.slice(start, i);
            
            if (isPalindrome(prefix)) {
                const partitions = partition(str, i);
                
                for (const part of partitions) {
                    result.push([prefix, ...part]);
                }            
            }
        }
    }
    
    return result.length
        ? result
        : [[]];
}

function partition(str, memo = {}) {
    const result = [];

    if (str) {
        if (memo[str]) {
            result.push(...memo[str])
        } else {
            for (let i = 1; i <= str.length; i++) {
                const prefix = str.slice(0, i);
                
                if (isPalindrome(prefix)) {
                    for (const part of partition(str.slice(i), memo)) {
                        result.push([prefix, ...part]);
                    }
                }
            }

            memo[str] = result;
        }
    }
    
    return result.length
        ? result
        : [[]];
}

function partition(str, memo = {}) {
    const result = [];

    if (str) {
        if (memo[str]) {
            result.push(...memo[str]);
        } else {
            for (let i = 1; i <= str.length; i++) {
            
                const prefix = str.slice(0, i);
            
                if (isPalindrome(prefix)) {
                    const partitions = partition(str.slice(i), memo);

                    if (partitions.length == 0) {
                        result.push([prefix]);
                    } else {
                        for (const part of partitions) {
                            result.push([prefix, ...part]);
                        } 
                    }  
                }
            }

            memo[str] = result;
        }
    } else {
        result.push([]);
    }
    
    return result;
}

Structured Programming Hallway Analogy

Imagine you’re given a key and sent into a hallway. All along the hallway are locked doors to rooms and right at the end of the hallway is the exit.

As you come to a door along the hallway, you put your key in it and see if it opens. If it does, you enter the room. Inside the room there might be more doors. You try your key to see if any open. If they do, you walk inside and take a look around. Once you are finished in a room and there are no more doors to try you calmly walk back out to the hallway and out of the exit. This is structured programming.

Now imagine the same scenario. This time you come to a room in the hallway and the door unlocks. Great, you think, and walk straight in. Upon entering the room the door locks behind you, the floor caves in and you find yourself falling into darkness. You are being ejected from the building via a trap door. Congratulations, you have encountered an early return.

If you are working on a large codebase, the code you write will be worked on by people many years after you've departed the company. Which building would you rather explore? Which building do you want to leave for them?

Visually: