c++ programming iteration and recursion

Question

I am looking for some quick tips on a homework assignment. We are given a few problems and have to write two quick programs on how to solve the problems with one each of iteration and recursion. I'm sure this is easier than I think, but I am getting easily confused over the two. By no means do I want anyone to fully solve the problems for me, I won't learn anything! But if you could look at what I have so far and let me know if I am heading in the right direction. Also, the code does not need to compile, our professor wants us to have a general idea of the differences of iteration vs. recursion.

Problem: check a string to see if it is a palindrome.

My solution- I think it is the iterative solution:

bool iterative_palindrome (const string& str) {
string line, result;
stack <char> stack_input;

//user enters string, program takes it
cout << "Enter string: " << endl;
while (getline (cin, line) && (line != "")) {

    //push string into stack
    for (size_t i = 0; i < line.size(); i++) {
        stack_input.push(line[i]);

        //create reverse of original string
        while (!stack_input.empty()) {
            result += stack_input.top();
            stack_input.pop();
            return result;
        }
        //check for palindrome, empty string
        if (line == result || line = "0" || line.empty()) {
            return true;
            cout << line << " is a palindrome!" << endl;
        } else {
            return false;
            cout << line << " is NOT a palindrome." << endl;
            cout << "Enter new string: " << endl;
        }
     }
  }
}

I remind everyone, I am pretty new to this stuff. I've read a few things already, but am still having a hard time wrapping my head around this.

line = "0" is an assignment not a comparison. Also, code after a return won't execute at all. — imreal
– imreal, Commented Nov 2, 2012 at 0:13
Are you being asked to use a stack? You are making this harder than it has to be. — Duck
– Duck, Commented Nov 2, 2012 at 0:19
Don't exactly have to use a stack, but our professor has spent a lot of time talking about them, that bit just kind of came to me after looking over lecture notes and slides. From what other users are saying, seems like you are right! — supersix3
– supersix3, Commented Nov 2, 2012 at 0:45

Eli Algranti · Accepted Answer · 2012-11-02 00:30:24Z

Here's the general idea:

Iterative: Initialize two pointers one pointer to the start and end of the string.

Compare the characters pointed, if different -> not palindrome.
Increase the start pointer and decrease the end pointer.
Repeat until start pointer >= end pointer.

Recursive (more difficult than iterative in this case):

End condition: A string of length zero or one is a palindrome.

A string is a palindrome if the first and last characters are the same and if the string without the first and last characters is a palindrome.

You can implement this recursive algorithm more efficiently by passing pointers to the first and last character in the string instead of copying the string between recursions.

Hope this helps :-)

snibbets · Accepted Answer · 2012-11-02 00:26:50Z

0

I figure writing code is the best way to explain the two approaches. Is this code understandable?

bool iterative_palindrome(const string& str) {
    int size = str.size();

    for (int i=0; i<str.size()/2; i++) {
        if (str[i] != str[size-i-1])
            return false;
    }

    return true;
}

You call this like recursive_palindrome(str, 0).

bool recursive_palindrome(const string& str, int index) {
    int size = str.size();

    if (index >= size/2)
        return true;

    if (str[index] == str[size-index-1])
        recursive_palindrome(str, index+1);
    else
        return false;
}

answered Nov 2, 2012 at 0:26

snibbets

1,14510 silver badges13 bronze badges

2 Comments

supersix3 Over a year ago

Thanks for a quick response - I can kind of see where you are going with this code. I am a bit confused over the part in the iterative solution where you have: "size()/2" - why are we dividing by two? Also, within the if statement, why are we subtracting [size-i-1]?

snibbets Over a year ago

I divide by 2 because you need to make only size/2 comparisons (one half of the string is being compared to the other half). The index is size-i-1 because this counts backwards from the end of the string. (Remember that the first index of a string is 0, not 1, so I need to subtract 1). Hope this clarifies it.

Collectives™ on Stack Overflow

c++ programming iteration and recursion

2 Answers 2

Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Related