C++

Forum

 
recursion error?

sultan0104 (12)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
#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
Last edited on
DizzyDon (121)
Your algorithm would be more like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
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:

1
2
3
4
5
6
 
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));
}

deleted account xyzzy (5768)
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#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 (11235)
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).
Last edited on
kbw (9488)
You could use a std::string_view and forget all that copy/erase nonsense.
1
2
3
4
5
6
 
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 (121)
I felt that string_view would just confuse the OP. Btw, palindrome is spelled with an i. :-)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#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 (12)
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)
Last edited on
DizzyDon (121)
You had two errors, the one you mention and also you forgot to return the value of the recursive call.
sultan0104 (12)
Oh yeah I didn't notice that, thanks though
seeplus (6591)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#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');
}

Topic archived. No new replies allowed.