• Post Reply Bookmark Topic Watch Topic
  • New Topic

using recursion  RSS feed

 
Lama Al Najjar
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was doing this question that is as follows.


A palindrome is a word that is the same when read either forwards or backwards. For example, both “wow” and “q” are both palindromes while “cat” is not. We can define a palindrome recursively as follows:
 The empty string "" is a palindrome.
 A single character (letter, number or symbol) is a palindrome.
 A string whose first and last characters are the same and the remaining string (when you remove the first and last characters) is also a palindrome is a palindrome.
Write a static method isPalindrome(String s) that returns true if the input string is a palindrome and false if not. Your method must be recursive. Be sure to test your function with several strings (some that are palindromes and some that are not
)

I appreciate your time to have a look at the code I came up with and check if my logic makes sense or no. It actually doesnt since my code doesn't work properly. Please give me some hints. Appreciated.

 
Campbell Ritchie
Marshal
Posts: 55772
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

When you are doing recursion you need three things: a base case, a reduction, and a way to put the whole lot together with the current test. Unfortunately, unlike other kinds of programming, it is difficult to take recursion apart; if you lose one of the parts it will not work; it may in fact run out of stack space and crash. I can see you have got at least two of those three parts wrong, I am afraid.

Start by looking at the base case and comparing it with the instructions you have been given. Then have a look at the reduction. How are you shortening the String?

Another thing: a lot of people will disagree with me, but I like structured programming. I like to see the keyword return not more than once per method.
 
Liutauras Vilda
Marshal
Posts: 4660
320
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A warm welcome to the Ranch first

First you need clearly define what is Palindrome.

Do you consider this as a palindrome adam, I’m Ada? Probably not, as number or symbol can be a palindrome on its own.
How about Ada, is it palindrome? Bear in mind, it says about characters. A is not the same as a. If you think Ada is a palindrome, then you need to think about converting character to lower case before you compare first with last.

Lama Al Najjar wrote:my code doesn't work properly
And please explain more about it. Doesn't work is the most inaccurate phrase. Did you get an error? If yes, what error? Code compiles, program runs, but produces unexpected results? What your expected results are? And what actual?
 
Campbell Ritchie
Marshal
Posts: 55772
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:. . . adam, I’m Ada . . .
I always knew that as Madam, I'm Adam. You would have to remove all spaces and punctuation to get MadamImAdam and then convert the whole thing to lower case. So let's assume the method receives madamimadam rather than Madam, I'm Adam. and will identify that as a palindrome.
 
bhshn bhwsr
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Issue is with the return stmt..... isPalindrome1(s.substring(n+1,s.length()));..........check the substring part..you will have to take care of start and end index......I think it should work after that.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lama Al Najjar wrote:Please give me some hints...

1. To understand recursion, you must first understand recursion.

It'a an old chestnut, and it sounds flippant; but I actually find it a very good analogy for "visualising" recursion.

2. A switch statement might make things a bit clearer. viz:Note I've simply converted the code you supplied (which is incorrect) to use switch; I haven't tried to change anything.

Hint: One thing that's wrong (and it's not the only one) is that you haven't incorporated the very first rule you were given - "The empty string "" is a palindrome" - into your method.

HIH

Winston
 
Lama Al Najjar
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
Lama Al Najjar wrote:Please give me some hints...


Hint: One thing that's wrong (and it's not the only one) is that you haven't incorporated the very first rule you were given - "The empty string "" is a palindrome" - into your method.


Can I consider this: if the length of the string is equal to one or below, therefore I have put the "empty string case" into account ?
 
Sam Knowski
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lama Al Najjar wrote:Can I consider this: if the length of the string is equal to one or below, therefore I have put the "empty string case" into account ?

One of the beautiful things about programming is that you can give 10 developers the same problem, and they can give you 10 different, correct, solutions. There are approaches to solving this problem both with and without directly accounting for the empty string case and the single character space. I would certainly encourage you to find multiple solutions to this problem and go with the one you feel is the least complex.

To more directly answer your question, in your current solution I would recommend handling the empty string case. You are very close to a solution with your current code. bhshn bhwsr gave you a great hint on where to look to correct your code, so please read his post again and see if you can see the problem. Also, as Campbell mentioned, using return multiple times in the same method can create problem when you write larger programs down the road, so getting in the habit of avoiding that pattern can potentially save you some major headaches.
 
Sam Knowski
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
To understand recursion, you must first understand recursion.

I'm going to steal this
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lama Al Najjar wrote:Can I consider this: if the length of the string is equal to one or below, therefore I have put the "empty string case" into account ?

Sure. Or in switch language (from above):However, your problems don't end there.

Another hint: What is n supposed to be (or do) in your method?

Winston
 
Campbell Ritchie
Marshal
Posts: 55772
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:. . . Another hint: What is n supposed to be (or do) in your method? . . .
That is only a minor problem; there is a much bigger problem elsewhere.
 
Puspender Tanwar
Ranch Hand
Posts: 471
2
Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
if you are using a recursive method, the method itself have a return statement. it shouldn't made handicapped by the return statement of if else clause(means method itself should have a return statement that is independent of if else clause ). so, just think how could you do this, only a little difference you need to do in your code
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!