Iteration to Recursion

Oct 29, 2017 at 12:42am
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
    }
}
Oct 29, 2017 at 8:53am
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.
Oct 29, 2017 at 5:23pm
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 Oct 29, 2017 at 7:29pm
Oct 29, 2017 at 6:40pm
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;
}
Oct 29, 2017 at 7:25pm
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 Oct 29, 2017 at 7:28pm
Oct 30, 2017 at 9:29am
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.