Recursive Functions

[cblack618]

Hello,

Can someone help me and walk me through the steps with this assignment. I'm a pure beginner and this is beyond my knowledge level. I didn't post any code becuase im not sure where to start beyond the preprocessor directives


For this assignment, you will create a program that tests a string to see if it is a palindrome. A palindrome is a string such as “madam”, “radar”, “dad”, and “I”, that reads the same forwards and backwards. The empty string is regarded as a palindrome. Write a recursive function:

bool isPalindrome(string str, int lower, int upper)

that returns true if and only if the part of the string str in positions lower through upper (inclusive at both ends) is a palindrome. Test your function by writing a main function that repeatedly asks the user to enter strings terminated by the ENTER key. These strings are then tested for palindromicity. The program terminates when the user presses the ENTER key without typing any characters before it.

[Duthomhas]

Think about how you would do it on paper. (Or, better yet, get out a piece of paper.)

Here is an example to play with.

Zappan
 L  U

We wish to determine if the string "appa" is a palindrome.

The way a recursive function works is to take part of a list and relate it to the remainder of the list. In this case, I can say that:

'a' == 'a'

and consequently all I need to do is ask if everything between those characters is a palindrome.

Zappan
  LU

Indeed,

'p' == 'p'

Once again, I modify my indices and ask again:

Zappan
  UL

We discover that upper ≤ lower, and conclude that the string IS a palindrome.

Try this with “madam”:

madam
L   U  yes, adjust indices, ask again:
 L U   yes, adjust indices, ask again:
  ↑    yes, adjust indices, ask again:
 U L   yes, done

Try this with a NON-palindrome:

abca
L  U  yes, adjust indices and ask again:
 LU   NO. done.

To do the “press ENTER twice to quit” trick is easy:

int main()
{
  std::string s;
  while (getline( std::cin, s ) && !s.empty())
  {
    ... test s for palindrome-ness
  }
}

Good luck!

[dhayden]

When writing a recursive function, I always code it like this:

if (base case) {
    do the base case;
} else 
    do the recursive case
}

This cleanly separates the two cases. More importantly, it makes you think about both of them separately. I learned through experience that it's too easy to concentrate on the recursive case and completely forget about the coding the base case. Then you end up with infinite recursion which can be hard to debug, especially for beginners.

Also, to help with debugging, print out the arguments of the call to ispalindrome. Once the code is working, remove those debugging lines.

Putting this together, your ispalindrome() would start like this:

bool isPalindrome(string str, int lower, int upper)
{
    cout << "isPalindrome(" << str << ',', << lower << ',' << upper << ")\n";
    if (base case) {  // what condition makes the base case?
          do the base case;    // what do you return in the base case?
   else {
          do the recursive case;
   }
}

Use Duthomhas's advice above to fill in the details.

[jonnin]

Everyone thinks differently. I 'find the loop', as recursion is a combination of a loop and a free stack data structure. Finding the loop of course means "what is the loop condition" (the base case) and "what is the loop body".

but you can also clarify the logic in your head by writing it in pseudo code.
a palindrome is the same forwards and backwards... so one way to do it is to reverse the string. one way to reverse things is a stack.
abcd
push a, push b, push c, push d.
pop d, pop c, pop b, pop a... its reversed!
now compare the reversed against the original... and it isn't a match.
then turn that to recursion, push until end of string (base case), hit base case and start popping, compare the popped against the original...
its not the best way to do it, of course, but its A way to do it and the point was a simple approach that you can see how the thinking goes. If you sit down with the problem you can find a more efficient solution, and the thinking is similar, but I felt you needed to see a simple approach not a weird one here.

It takes a while to really understand recursion. First, its weird when you first see it, and its hard at first to mentally track the stack state against the problem state to get it right. Second, its usually taught poorly, on problems where the recursion is not needed or downright silly (eg factorials or palindromes, both of which are easier to solve without recursion). There are problems where doing it without recursion is much harder. There are, as far as I know, no problems that can be solved with recursion that can't be solved without it (and many languages do not support it at all) -- one of the KEY ideas of recursion is being able to spot when a problem is easier with it than without.

one example of recursion that is easier than without is deletion of every item in a linked list. Push all the way to the end and delete as you pop back out becomes 2 lines of code. Doing the same in a loop is a minor aggravation (its not 'hard' but its not 2 lines either).

[cblack618]

Hello,

So now I'm confused about what a base case is and how to do that part ? Also not quite sure what my if else condition statement should be

// Charles Blackwell CIS 221 M5 ASSIGNMENT

#include <iostream>
#include <string>

using namespace std;

bool isPalindrome(string str, int lower, int upper)
{
    cout << "isPalindrome(" << str << ',', << lower << ',' << upper << ")\n";
    if (base case) {  // what condition makes the base case?
        do the base case;    // what do you return in the base case?
    else {
        do the recursive case;
    }
    }

[cblack618]

This is another version I have but it's not right and not sure what I'm doing

//CIS 221 M5 assignment
#include <iostream>
#include <string>

using namespace std;

bool isPalindrome(string str, int lower, int upper);

int main()
{
	string word;

	cout << "Enter a word to see if its a palindrome" << endl;
	getline(cin, word);

	if (isPalindrome(word))
		cout << word << " : is a palindrome." << endl;
	else
		cout << word << " : is not a palindrome." << endl;

	return 0;

}

bool isPalindrome(string str, int lower, int upper);

if (string.length() <= 1)
return 0;

return (string[0] == string[string.lenght() -1])

[Repeater]

Well, for starters, a recursive function needs to call itself again, yes?

bool isPalindrome(string str, int lower, int upper) // NO SEMI_COLON
{ // YOU FORGOT THE OPENING BRACE

if (string.length() <= 1)
return 0;

return (string[0] == string[string.length() -1])
} // YOU ALSO FORGOT THE CLOSING BRACE 

Putting aside the mess you made of writing the function (semi-colon, braces missing), this function isn't calling itself, is it?

You need isPalindrome to do one of two things; return a value, or call itself.

Can you think of when it should return a value, and when it should call itself again?

[cblack618]

Hi Repeater,

I did mention I'm a beginner =))))))))))))))))))))))

All i know is that a recursion function calls itself

//CIS 221 M5 assignment
#include <iostream>
#include <string>

using namespace std;

bool isPalindrome(string str, int lower, int upper);

int main()
{
	string word;

	cout << "Enter a word to see if its a palindrome" << endl;
	getline(cin, word);

	if (isPalindrome(word))
		cout << word << " : is a palindrome." << endl;
	else
		cout << word << " : is not a palindrome." << endl;

	return 0;

}

bool isPalindrome(string str, int lower, int upper)
{
	if (string.length() <= 1)
		return 0;

	return (string[0] == string[string.lenght() - 1])

		isPalindrome;
}

[Repeater]

I did mention I'm a beginner =))))))))))))))))))))))

It's a beginner question. Although it looks like you're too much of a beginner to be trying to write clever funtions. Looks like you need to learn how to call a function first.

bool isPalindrome(string str, int lower, int upper)
{
	if (string.length() <= 1)
		return 0;

	return (string[0] == string[string.lenght() - 1])

		isPalindrome; // WRONG
}

The line I've marked WRONG. Can you see that that is NOT calling a function? Do you know how to call a function?

If not, you need to go back a few steps and first learn what a function is, and how to call a function.

[cblack618]

IsPalindrome();

?????

[Duthomhas]

I can’t stand threads about recursive functions.

@cblack618

There isn’t anything special or scary about a recursive function. It is all in people’s heads.

Think it through:


Given two indices into a string (which asks for a substring), you have a simple either/or question:

  • Are the indices invalid?
  • Are the indices valid?

If the indices are invalid (upper < lower), you are dealing with an empty substring — which is YES a palindrome. (The empty string is a palindrome.)

You can even extend this. Given a substring of length 1 (like "a") then you clearly have a palindrome. ("a" is a palindrome, just like "".)

You can revise your question:

  • If (upper <= lower) then YES (it is a palindrome)
  • else maybe?

Here is the basis of any recursive function. Test a terminal condition (in this case, can I say that I definitely do or do not have a palindrome) and terminate. Otherwise we have more questions to ask:

bool isPalindrom(string str, int lower, int upper)
{
  if (upper <= lower) return true;
  // else maybe?
}

Now we can consider the maybe part: do the characters at the indexed places match (does str[lower] == str[upper])?

Let’s make this another question:

  • do the two indexed characters match equal?
  • do the two indexed characters match unequal?

If they are unequal, then you cannot have a palindrome.
Otherwise you are at another maybe.

bool isPalindrom(string str, int lower, int upper)
{
  if (upper <= lower) return true;
  // test the next possibility (is it NOT a palindrome?)
  // else maybe?
}

But here is where life gets easy. You have already answered the question for the maybe!
Simply adjust the indices and ask the same palindrome questions again!

Eventually you will either find a mismatch (not a palindrome) or an empty/single-character string (yes a palindrome).


It takes a little practice being able to order the questions properly. For example, the first question, valid or invalid indices — we test whether they are invalid first because that gives us an immediate answer to the question “is-it-a-palindrome?”

If we had tested whether they were valid we would be playing with the “maybe” part, which is too much to think of first.

In other words, the questions we ask are designed to chip away at that maybe until there is nothing left. This is the point of recursion. Chip everything away until we can just keep asking the same questions over and over on a simpler or smaller piece of the problem.

madam
↑   ↑ it is not (not a palindrome)
 ↑↑↑  maybe it is
 ada
 ↑ ↑  it is not (not a palindrome)
  ↑   maybe it is
  d   it is definitely a palindrome

Hope this helps.

[cblack618]

This is what I tried based on the info u gave me but not sure

//CIS 221 M5 assignment
#include <iostream>
#include <string>

using namespace std;

bool isPalindrome(string str, int lower, int upper);

int main()
{
	string word;

	cout << "Enter a word to see if its a palindrome" << endl;
	getline(cin, word);

	if (isPalindrome(word))
		cout << word << " : is a palindrome." << endl;
	else
		cout << word << " : is not a palindrome." << endl;

	return 0;

}

bool isPalindrome(string str, int lower, int upper)
{
	if(upper <= lower) 
	return true;
	
	else 
	(str[lower] == str[upper])

	return false;
	
	
		
}

[Duthomhas]

You are going to have to work on your C++ syntax. If you need help with the basics you can get tutoring at your university’s help center, or visit with your professor for him to give you some tips on how to catch up, or read some online tutorials to get you up to speed.

Programming is not like other computer uses, where the computer helps you do stuff. You have to carefully think your way through every problem, then instruct the computer what to do. This implies two things: you must understand your problem in a step-by-step logical train of thoughts, and you must understand how to talk to the computer (in this case, by writing valid C++ code). It is a rough learning curve, and not one that takes well to having procrastinated any.

I am not trying to be cruel, but this problem is literally so simple that I cannot help further without just giving you the solution. You have to struggle with it until your brain bends enough to get it. It will happen, if only you struggle through it.

Good luck!

[cblack618]

Well geez

[Repeater]

It is all in people’s heads.

Very much. Recursive functions are not inherently difficult, but people seem to try to write them by trial and error. Without thinking. Without understanding the nature of recursive functions.

They either return a value, or they call themselves again WITH DIFFERENT PARAMETERS.

That's it. That's all there is to it.

At risk of repeating Duthomhas (the clue's in my name!), it's just a matter of thinking methodically.

How will this function work? One way to think about it is to work out the basics of the actual recursive bit first. To simply write code that does nothing more than the actual full recursion. So what does this recursive function do?

We'll take a string:
someInputString

We will compare the first and last letters:
someInputString

Then we will compare the second and second-to-last letters:
someInputString

Then the next:
someInputString

And so on. We will keep going, until we've compared all the pairs of letters.

bool isPalindrome(string str, int lower, int upper)
{
   if (compared all the letters already)
  {
    return true;
  }
  else
  {
    return isPalindrome(str, lower + 1, upper -1) // Call function again, on the next pair of letters
  }
}

That's the basics of the recursive function. That's it. All that's left is to fill in the condition (compared all the letters already) and to add one more thing; return false; for the case where the letters being compared actually don't match.

[cblack618]

//CIS 221 M5 assignment
#include <iostream>
#include <string>

using namespace std;

bool isPalindrome(string str, int lower, int upper);

int main()
{
	string word;

	cout << "Enter a word to see if its a palindrome" << endl;
	getline(cin, word);

	if (isPalindrome(word))
		cout << word << " : is a palindrome." << endl;
	else
		cout << word << " : is not a palindrome." << endl;

	return 0;

}

bool isPalindrome(string str, int lower, int upper)
{
	if(upper <= lower) 
	{
		return true;
	}
	else 
	{
		return isPalindrome(str, lower +1, upper-1)
	}
	
	isPalindrome(string str, int lower, int upper);
		
};

[Repeater]

bool isPalindrome(string str, int lower, int upper)
{
	if(upper <= lower) 
	{
		return true;
	}
	else 
	{
		return isPalindrome(str, lower +1, upper-1)
	}
	
	isPalindrome(string str, int lower, int upper);
		
};

When will that second call to isPalindrome ever be called? The one on line 12 there in the code I copied from you.

And now add a return false. Can you think of what the condition should be? How can you tell that the word isn't a palindrome?

[cblack618]

1) I’m not sure about the line 12 question you asked.

2) I added a return false. Not sure what the condition should be

3) a word isn’t a palindrome if it’s not the same spelled backwards.

//CIS 221 M5 assignment
#include <iostream>
#include <string>

using namespace std;

bool isPalindrome(string str, int lower, int upper);

int main()
{
	string word;

	cout << "Enter a word to see if its a palindrome" << endl;
	getline(cin, word);

	if (isPalindrome(word))
		cout << word << " : is a palindrome." << endl;
	else
		cout << word << " : is not a palindrome." << endl;

	return 0;

}

bool isPalindrome(string str, int lower, int upper)
{
	if(upper <= lower) 
	{
		return true;
	}
	else 
	{
		return isPalindrome(str, lower +1, upper-1)
	}
	
	isPalindrome(string str, int lower, int upper);
	
	return false;
		
};

[Repeater]

1) I’m not sure about the line 12 question you asked.

Well then get sure. Look at the code. Can you figure out a way that the execution can get to the line in bold (below), that YOU wrote. YOU put it there. Can you see a way for the execution to get there? Tell me a value of str, lower and upper that will cause the lines in bold to be reached.

Thus far, you're just copying what other people have written and mixing it round and round. You need to think.

isPalindrome(string str, int lower, int upper)
{
	if(upper <= lower) 
	{
		return true;
	}
	else 
	{
		return isPalindrome(str, lower +1, upper-1)
	}
	
	isPalindrome(string str, int lower, int upper);
	
	return false;
		
};

3) a word isn’t a palindrome if it’s not the same spelled backwards.

The function has str, upper and lower.

Here, look at this again.

We'll take a string:
someInputString
We will compare the first and last letters:
someInputString

Is there something about that comparison, about those two letters, about the s and the g , that tells you if the word is a palindrome or not?

[cblack618]

Hi,

I hear you, but I’m a very beginner at C++ and don’t really know what I’m doing. I’m in a online c++ College class and this is the assignment and there’s not much opportunity to get help from the teacher.