# Recursive vs. Iterative Palindrome Check

A word, phrase, or sequence that reads the same backwards as forwards, e.g. madam.

For this challenge we will investigate two algorithms used to find out if a word is a palindrome or not. The first algorithm will use an iterative approach, the second algorithm will use a recursive approach.

#### Iterative Approach

An iterative approach is based around the use of a loop which can be:

• A count-controlled loop (e.g. FOR loop)
• A condition-controlled loop (e.g. WHILE loop or REPEAT UNTIL loop)

For our iterative palindrome check algorithm, we will use a loop to check all the letters in the first half of the word and compare them with the letters in the second half of the word (in reverse order). If they all match then the word is a palindrome.

#### Recursive Apporach

A recursive function is a function that:

• Includes a call to itself,
• Has a stopping condition to stop the recursion.

For our recursive palindrome check algorithm, we will use a function that:

• Checks that the word is at least two characters long:
• If the word is less than two characters then the function will stop the recursion (stopping condition) and Return True as the word is a palindrome.
• If the word is two or more characters long, the function will check that the first and last letter of the word are the same:
• If they are the same, the function will extract the word in the middle (remove the first and the last letter) and call itself with this new shortest word.
• If they are different, then the word is not a palindrome. The function will stop the recursion here (stopping condition) and return False.

You can visualise/trace this recursive function on recursionvisualizer.com

Complete the following factorial challenge using both an iterative approach and a recursive approach.
[pms-restrict display_to=”not_logged_in” message=” “]

#### Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
[/pms-restrict] [pms-restrict subscription_plans=”14217″ message=” “]

#### Solution...

You are viewing this solution as part of your full membership subscription!

Iterative ApproachRecursive Approach

#### Iterative Approach: Python Code

```#Iterative Palindrome Check – Iterative Approach

def isPalindrome(word):
midPoint = len(word)//2
palindrome = True
for i in range(0,midPoint):
left = word[i]
right = word[len(word)-i-1]
if left!=right:
palindrome=False
break
return palindrome

word = input("Enter a word or sentence:")
#Length check - we need a word of at least 2 characters
while len(word)<2:
word = input("Try again - Enter a word or sentence with at least 2 characters.")

if isPalindrome(word):
print("This is a palindrome.")
else:
print("This is not a palindrome.")
```

#### Recursive Approach: Python Code

```#Recursive Palindrome Check – Recursive Approach

def isPalindrome(word):
if len(word)<2:
return True   # Stop the recursion
else:
firstLetter = word[0]
lastLetter = word[len(word)-1]
if firstLetter == lastLetter:
middleWord = word[1:len(word)-1]
print(firstLetter + "==" + lastLetter)
print("Now checking if '" + middleWord + "' is a palindrome.")
return isPalindrome(middleWord)  #recursive call
else:
print(firstLetter + "!=" + lastLetter)
return False   # Stop the recursion

word = input("Enter a word or sentence:")
#Length check - we need a word of at least 2 characters
while len(word)<2:
word = input("Try again - Enter a word or sentence with at least 2 characters.")

if isPalindrome(word):
print("This is a palindrome.")
else:
print("This is not a palindrome.")
```
[/pms-restrict]

Did you like this challenge?

Click on a star to rate it!

Average rating 4.9 / 5. Vote count: 14

No votes so far! Be the first to rate this post.

As you found this challenge interesting...

Follow us on social media!

Tagged with: ,