Recursion exercises

[mpg]

I have thes 3 exercises but I have problems with this new argument about recursion in c++:
1) int s (int n) returns the sum of the first n odd numbers
2) int f (int n) returns the sum of the first n natural numbers
3) bool pal (string t) determines if the string t is palindrome.

The second but doesn't work..

#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>

using namespace std;


int somma(int n)
{if (n<=0)
return 0;
else
return n+somma(n-1);
}

int main()
{
int n;
cin>>n;
cout<<somma(n);
}

with number 3 I know what I can do without recursion but I can do it with recursion..

#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
using namespace std;

bool pal(string s)
{int i=0, l = s.length(); int j = l-1;
while ( (i<=j) )
  {
   if (s[i]!=s[j])
    {return false;}
   else
    {i=i+1; j=j-1;}
  }
return true;
}
int main()
{
    string s;
    cin>>s;
    cout<<pal(s);
}

 

[keskiverto]

bool pal( string s )
{
  // first and last character could mismatch; s.front(), s.back()

  // is s.substr( 1, s.size()-2 ) a palindrome
}

first n odd numbers

The sum of 1, 3, 5, ...

But, you compute now the sum of n, n-1, n-2, ...

Q: If you have n odd numbers, is the largest of them 2*n-1?

[mpg]

I haven't done at school "substr" can you have another solution for the palindrome?

[keskiverto]

Your function takes only one parameter, a string object. How to pass necessary data with that object?
Use of substring is a solution.

Read: http://www.cplusplus.com/reference/string/string/substr/

[mpg]

But I can't use if I haven't studied it at school....... there isn't another solution?

[keskiverto]

Of course there are. Look at the description of substr. What does it do?

Is there anything that you have studied at school that can do similar thing as the substr?

[mpg]

I can't be able to find another mode.. can you help me?

[George P]

Can you do a for loop (or a while or do/while loop) to access the individual elements in your string?

Walk from the beginning of the string to the half-way point*, comparing the first and last elements, then the second and second to last elements. Lather, rinse and repeat until you reach the mid-point in your string, or one of the equality comparisons fails and the string isn't a palindrome.

You will have to check for spaces and other non-alphabetic characters and skip over them for your palindrome check.

You also have to be concerned whether the characters being compared have an upper/lower case mismatch.

Creating a copy of the string with only alphabetic characters before you check for palindrome status is also something you can do.

*Why the half-way point? You are comparing elements at both ends, working towards the middle. Going past half-way is excessive since you've already found the string is or isn't a palindrome. If the string has an odd-number of elements then the final check is comparing the middle element with itself.

[JLBorges]

Trivial palindrome checker (case sensitive, does not ignore punctuation, space):

#include <string>

bool pal( const std::string& str, std::size_t left, std::size_t right )
{
    if( right <= left ) return true ;
    else if( str[left] != str[right] ) return false ;
    else return pal( str, left+1, right-1 ) ;
}

bool pal( const std::string& str )
{
    if( str.empty() ) return true ;
    else return pal( str, 0, str.size()-1 ) ;
}

[lastchance]

Ignores non-alphanumerics and differences in case:

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

bool isPalindrome( const string &str, int left = -1, int right = 0 )
{
   if ( left < 0 ) return isPalindrome( str, 0, str.size() - 1 );
   while ( left <= right && !isalnum( str[left ] ) ) left++;
   while ( left <= right && !isalnum( str[right] ) ) right--;
   return right <= left || (  tolower( str[left] ) == tolower( str[right] ) && isPalindrome( str, left + 1, right - 1 )  );
}

int main()
{
   string tests[] = { "", "?:!", "c", "A man, a plan, a canal, panama!", "tata", "a232", "a232a" };
   for ( string s : tests ) cout << s << "  ---->  " << boolalpha << isPalindrome( s ) << '\n';
}