재귀를 활용하여 회문인지 판단하기

회문(palindrome)은 앞에서 읽든 뒤에서 읽든 똑같은 단어입니다. 예를 들어 rotorredder는 회문이지만 motor는 회문이 아닙니다.
어떤 단어가 회문인지 아닌지를 판단하기 위해 재귀법을 어떻게 활용할 수 있을까요? 탈출 조건이 무엇인지 알아보는 것부터 시작합시다. 단어 a를 생각해 봅시다. 이는 회문입니다. 사실 회문을 영어로 된(또는 여러분이 고려하고자 하는 언어 무엇이든) 실제 단어로 생각해야 할 필요는 없습니다. 회문을 그냥 xyzyzyx처럼 앞쪽이든 뒷쪽이든 어느 쪽으로 읽든 똑같은 연속된 문자로 생각할 수 있습니다. 연속된 문자를 문자열이라고 합니다. 그러므로 글자 하나만으로 된 문자열은 기본적으로 회문이라고 할 수 있습니다. 문자열에 아무 글자가 없을 수도 있습니다. 0개의 글자로 된 문자열을 빈 문자열(empty string)이라고 합니다. 빈 문자열 역시 회문입니다. 왜냐하면 앞쪽으로 읽든, 뒤쪽으로 읽든 똑같이 읽히기 때문이죠. 그러므로 최대 하나의 글자를 포함하는 문자열은 회문이라고 합시다. 따라서 빈 문자열이나 글자가 하나인 문자열도 회문이라는 것이 여기에서의 탈출 조건입니다.
문자열이 두 개 이상의 글자로 이루어진 경우는 어떨까요? 이것이 재귀적인 경우가 됩니다. 회문인 rotor를 생각해 봅시다. 첫 번째와 마지막 글자가 같으며 이 특성은 어느 회문에서나 마찬가지입니다. 반대로 motor와 같이 첫 번째와 마지막 글자가 같지 않다면 그 문자열은 회문일 수가 없습니다. 그러므로 이제 어떤 문자열이 회문이 아니라는 것을 단언할 수 있는 방법이 생겼습니다? 첫 번째와 마지막 글자가 다를 경우입니다. 이런 상황에서는 답이 즉각적으로 나오기 때문에 또다른 탈출 조건으로 간주할 수 있습니다. 첫 번째와 마지막 글자가 같을 경우로 돌아갑시다. 두 글자가 같으면 이는 무엇을 의미할까요? 문자열이 회문일 수도 있고, 아닐 수도 있다는 것입니다. 문자열 rater는 첫 번째와 마지막 글자는 같지만 회문은 아닙니다. 첫 번째와 마지막 글자를 제외하면 문자열 ate가 남습니다. 남은 문자열의 첫 번째와 마지막 글자가 같지 않으므로 rater는 회문이 아님을 알 수 있죠.
이제 어떤 문자열이 회문인지 여부를 재귀적으로 알아낼 수 있게 되었습니다. 첫 번째와 마지막 글자가 다르면 그 문자열은 회문이 아니라고 합니다. 그렇지 않다면 첫 번째와 마지막 글자를 제외하고 남은 문자열—하위 문제—가 회문인지 알아봅니다. 짧아진 문자열의 해답이 원래 문자열의 해답이 되도록 합니다. 더 이상 비교할 글자가 없거나 하나만 남게 되면 그 문자열은 회문입니다. 이것이 위에서 다뤘던 두 단어를 해결하는 과정입니다.
이를 의사 코드(Psudocode) 로 어떻게 작성할 수 있을까요?
  • If the string is made of no letters or just one letter, then it is a palindrome.
  • Otherwise, compare the first and last letters of the string.
  • If the first and last letters differ, then the string is not a palindrome.
  • Otherwise, the first and last letters are the same. Strip them from the string, and determine whether the string that remains is a palindrome. Take the answer for this smaller string and use it as the answer for the original string.

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.