Iteration to Recursion

I'm having trouble with iteration to recursion. I looked at many forums and articles (including the one on this site) about recursion, but I just don't really understand it. How would I change this to a recursion function?

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
int main() 
{
    string word;
    string result;
    char lower;
    stack<char> pali;
    cout << "Please input a word" << endl;
    cin >> word;
    for(size_t i = 0; i < word.size(); i++) //for loop
    {
        lower = word[i]; //setting char lower equal to the char in word[i]
        word[i] = tolower(lower); //word[i] is equal to the lowercase of variable lower (so as not to get messed up by uppercase letters)
        pali.push(word[i]); //setting the stack pali equal to each char in word
    }
    while(!pali.empty()) //while stack pali isn't empty
    {
        result += pali.top(); //result equal result plus char on top of stack pali
        pali.pop(); //popping of the top char on stack pali
    }
    
    cout << "Word input: " << word << endl; //output
    cout << "Word backwards: " << result << endl; //output
        
    if(result == word) //if the variable result equals the variable word
    {
        cout << "This word is a palindrome." << endl; //output
    }else{
        cout << "This word is not a palindrome." << endl; //output
    }
}
One way to see recursion is that you have a function that takes some amount of data.
If the received dataset is empty, then function does not need to recurse any deeper.

The function splits the data into two subsets.
It will process (small) subset itself, but it will call itself with the other subset.

For example, taking one character from a word, doing something with it, and letting recursive call handle the rest of the word.
Something like this? Though, when it gets to the while statement, it does not put the chars in pali into variable result, therefore making the program output that it is not a palindrome even if it is...
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
35
36
37
38
39
void Palindrome(size_t i)
{
    string word;
    char lower;
    stack<char> pali;
    for(size_t i = 0; i < word.size();) //for loop
    {
        lower = word[i]; //setting char lower equal to the char in word[i]
        word[i] = tolower(lower); //word[i] is equal to the lowercase of variable lower (so as not to get messed up by uppercase letters)
        pali.push(word[i]); //setting the stack pali equal to each char in word
        Palindrome(i++);
    }
}

int main() 
{
    string word = "";
    string result;
    stack<char> pali;
    cout << "Please input a word" << endl;
    cin >> word;
    for(size_t i=0;i < word.size(); i++)
    {
        Palindrome(i);
    }
    while(!pali.empty())
    {
        result += pali.top();
        pali.pop();
    }
    cout << "Word input: " << word << endl; //output
    cout << "Word backwards: " << result << endl; //output
    if(result == word) //if the variable result equals the variable word
    {
        cout << "This word is a palindrome." << endl; //output
    }else{
        cout << "This word is not a palindrome." << endl; //output
    }
}
Last edited on
will call itself with the other subset.

For example:
1
2
3
4
5
6
void foo( const std::string & word ) {
  if ( word.empty() ) return;
  char bar = word.front();
  foo( word.substr( 1 ) ); // call itself. Recurse.
  std:.cout << bar;
}
Oops, I forgot to add one part before I submitted it. It still does not run as it should when I have it like this.
1
2
3
4
5
6
7
8
9
10
11
12
13
void Palindrome(size_t i)
{
    string word;
    char lower;
    stack<char> pali;
    for(size_t i = 0; i < word.size();) //for loop
    {
        lower = word[i]; //setting char lower equal to the char in word[i]
        word[i] = tolower(lower); //word[i] is equal to the lowercase of variable lower (so as not to get messed up by uppercase letters)
        pali.push(word[i]); //setting the stack pali equal to each char in word
        Palindrome(i++);
    }
}

Last edited on
Line 3 creates an empty word. The word.size() is thus 0 and the loop never executes.

Line 5 creates a stack that is discarded at the end of the function.

Line 6 declares i that masks i. You can call the function with whatever parameter, but the loop does not care.

Your task was to replace (some) loops (and stack) with recursive functions.
Topic archived. No new replies allowed.