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.
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.