recursion error?

[sultan0104]

I made a code to check if a string is a palindrome. It works just fine for non-palindromes, but it outputs an error that goes along the line "terminate call after std::out_of_storage" when the inputted string is a palindrome. Here's the code.

#include <bits/stdc++.h>
using namespace std;

bool tesPal(string s) 
{
	if (s.length() < 2) {
		return true;
	} else {
		if (s[0] == s[s.length() - 1]) {
			s.erase(s[s.length() - 1], 1);
			s.erase(s[0], 1);
			tesPal(s);
		} else {
			return false;
		}
	}
}

int main() 
{
	string s;
	cin >> s;
	if (tesPal(s)) {
		cout << "YA";
	} else {
		cout << "BUKAN";
	}
}

Thanks

[DizzyDon]

Your algorithm would be more like this:

bool tesPal(string s) 
{
    if (s.length() < 2) {
        return true;
    } else {
        if (s[0] == s[s.length() - 1]) {
            s.erase(0, 1);
            s.erase(s.size() - 1, 1);
            return tesPal(s);
        } else {
            return false;
        }
    }
}

However, it would be better like this:

bool tesPal(string s) 
{
    if (s.length() < 2) return true;
    if (s[0] != s[s.size() - 1]) return false;
    return tesPal(s.substr(1, s.size() - 2));
}

[George P]

Your include statement is non-standard C++, Not every compiler has it, don't use it. It is for internal use by the compiler only. Include <iostream> and <string> instead.

Erasing string elements is dangerous. If the checked string is a palindrome eventually the repeated recursion will erase from an empty string causing an exemption to be thrown.

There is no need to use recursion, iterating through a string is not that hard:

#include <iostream>
#include <string>

bool isPalindrome(std::string str)
{
   size_t j  {str.length() - 1 };

   for (size_t i { }; i < j; i++, j--)
   {
      if (str[i] != str[j])
      {
         return false;
      }
   }

   return true;
}

int main()
{
   std::string words[5] = { "mom", "radar", "level", "hello", "one" };

   for (size_t i { }; i < 5; i++)
   {
      if (isPalindrome(words[i]))
      {
         std::cout << words[i] << " -> Palindrome\n";
      }
      else
      {
         std::cout << words[i] << " -> Not a Palindrome\n";
      }
   }
}

mom -> Palindrome
radar -> Palindrome
level -> Palindrome
hello -> Not a Palindrome
one -> Not a Palindrome

Something to consider, palindromes can be more than one word. "Madam, I'm Adam" is a classic example. Punctuation, spaces and capitalization of words needs to be dealt with when determining if a string is a palindrome.

[Peter87]

The first argument to erase is the index position of the character that you want to remove.

You also forgot to always return something. My compiler says:

warning: control reaches end of non-void function

If you're using Clang or GCC you can enable this and many other useful warnings by using the -Wall compiler flag (you might also want to use -Wextra for even more warnings).

[kbw]

You could use a std::string_view and forget all that copy/erase nonsense.

bool palendrome(std::string_view str) {
    if (str.size() < 2)
        return true;

    return str[0] == str[str.size() - 1] && palendrome({str.data() + 1, str.size() - 2});
}

[DizzyDon]

I felt that string_view would just confuse the OP. Btw, palindrome is spelled with an i. :-)

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

bool pal(string_view s) 
{
    return s.size() < 2 ||
           (s.front() == s.back() && pal({&s[1], s.size() - 2}));
}

int main() 
{
    string s;
    while (cout << "Enter string: ", getline(cin, s))
        cout << (pal(s) ? "Yes" : "No") << '\n';
    cout << '\n';
}

[sultan0104]

Okay thanks guys, all of your suggestions worked, i think my problem was the erase function (I didnt write the index, instead I wrote the character of the index)

[DizzyDon]

You had two errors, the one you mention and also you forgot to return the value of the recursive call.

[sultan0104]

Oh yeah I didn't notice that, thanks though

[seeplus]

#include <iostream>
#include <string>
#include <string_view>
#include <iomanip>

bool pal(std::string_view s) {
    return s.size() < 2 ||
        (s.front() == s.back() && pal({s.begin() + 1, s.end() - 1}));
}

int main() {
    for (std::string s;
        std::cout << "Enter string: " && std::getline(std::cin, s);
        std::cout << std::boolalpha << pal(s) << '\n');
}