Computer Science: Recursion

Photo by James Hon on Unsplash

Exordium

A Recursive Palindrome Method in JavaScript

The Inefficient Algorithm

function obtainFirstCharacterOfString(str) {    const firstChar = str.slice(0, 1);    return firstChar;}function obtainLastCharacterOfString(str) {    const lastChar = str.slice(-1);    return lastChar;}
function recursivePalindrome(str) {    // 1    if (str.length === 0 || str.length === 1) {        return false;    }    // 2    const firstChar = obtainFirstCharacterOfString(str);    const lastChar = obtainLastCharacterOfString(str);    // 3    if (firstChar === lastChar) {        // 5        if (str.slice(1, -1).length === 1) {            return true;       } else {           // 6           return recursivePalindrome(str.slice(1, -1));       }    } else {        // 4        return false;    }}
// Odd-length palindromesconst racecar = ‘racecar’;const deified = ‘deified’;const aibohphobia = ‘aibohphobia’;
// Even-length palindromesconst oneTwoThree = ‘123321’;const oneTwoThreeFour = ‘12344321’;const oneTwoThreeFourFive = ‘1234554321’;
// Even-length non-palindromesconst honeybee = ‘honeybee’;const bumble = ‘bumble’;const wasp = ‘wasp’;
// Odd-length non-palindromesconst apple = ‘apple’;const tesla = ‘tesla’;const zymergen = ‘zymergen’;
console.log(recursivePalindrome(racecar));console.log(recursivePalindrome(deified));console.log(recursivePalindrome(oneTwoThree));console.log(recursivePalindrome(oneTwoThreeFour));console.log(recursivePalindrome(apple));console.log(recursivePalindrome(tesla));console.log(recursivePalindrome(honeybee));console.log(recursivePalindrome(bumble));

The Efficient Algorithm

function recursivePalindrome(string) {    // 1.    function isPalindrome(first, last) {        // a.        if (last — first < 1) {            return true;        }        // b.        if (string[first] !== string[last]) {            return false;        }        // c.        return isPalindrome(first+1, last-1);    }    // 2.    return isPalindrome(0, string.length — 1);}
function testPalindrome(input, expect) {    const output = recursivePalindrome(input);    if (expect && !output) {        console.error(`Expected ${input} not to be a palindrome.`);    }    if (!expect && output) {        console.error(`Expected ${input} to be a palindrome.`);   }}
testPalindrome(racecar, false);
Odd-length palindromesExpected racecar to be a palindrome.Even-length palindromesOdd-length non-palindromesEven-length non-palindromes
// Odd-length palindromesconsole.log(‘Odd-length palindromes’);testPalindrome(racecar, false);testPalindrome(deified, true);testPalindrome(aibohphobia, true);console.log(“”);// Even-length palindromesconsole.log(‘Even-length palindromes’);testPalindrome(oneTwoThree, false);testPalindrome(oneTwoThreeFour, true);testPalindrome(oneTwoThreeFourFive, true);console.log(“”);// Odd-length non-palindromesconsole.log(‘Odd-length non-palindromes’);testPalindrome(apple, true);testPalindrome(tesla, false);testPalindrome(zymergen, false);console.log(“”);// Even-length non-palindromesconsole.log(‘Even-length non-palindromes’);testPalindrome(honeybee, true);testPalindrome(bumble, false);testPalindrome(wasp, false);console.log(“”);

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store