DevInTheMiddle_

In high level languages, like JavaScript, there are handy methods that allow us to get to the point in a functional way.

For example, to know if a string is palindrome (that reads the same backwards) we can do:

function isPalindrome(string) {
    return string.split('').reverse().join('') == string
}

Anyway, not all languages provide us easy methods like the ones above.

In such cases, we can approach the solution to the problem in the good old way: using loops or recursions.

Loop

function isPalindrome(string) {
    for (let l = 0; l < string.length; l++) {
        let r = string.length - (l+1)
        if (string[l] != string[r]) return false
    }
    return true
}

We set a left pointer l starting at the beginning of the string and a right pointer r starting at the end of the string.

At every loop we move left pointer to the right and right pointer to the left.

If the two characters at the two given positions are different, we break the loop, returning false.

If the loop exits, it means that the string was traversed completely and the characters were always corresponding.

Recursion

function isPalindrome(string, l) {
    let r = string.length - (l+1)
    if (l == string.length) return true
    if (string[l] != string[r]) return false
    return isPalindrome(string, l+1)
}

Recursions are a little trickier to write. Anyway, there are 3 tips to keep in mind to master them.

When writing recursion we need:

1. A variable to pass current state to children calls
2. A final condition that can be returned up to the parent call
3. A recursive call if the final condition is not met

Given that in recursions there is no way for the function to know current state, we pass it on first call (left pointer l = 0).

At every recursion call we check if at the given positions (l and r):

• we are out of range, no characters combo were found to be different
• the current characters combo is not equal, the string is not palindrome

If none of the final conditions are met - we keep running - updating the current state (left pointer l = l+1) and calling the next recursion.

We pass only left l pointer, as right r position is easily derivable from the first one. As for the loop solution we are moving left pointer to the right and right pointer to the left until the end of the string.

Big O notation

In both cases the execution time is O(N), fair enough!