• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

recursive palindrome

 
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have the following code to check for five characters palindrome but it always give me incorrect answer that if i have a word like radar the answer it isn't a palindrome. and if i changed any thing in the code i got either stack overflow or index out of bounds exception

the code is as the following
 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This code is confusing. What is the 2nd parameter to "compare" supposed to do? Why is it hardcoded to 2? And why is "last" hardcoded to 4? - shouldn't it initially be the index of the last character, i.e. the length of the word - 1?

And I doubt that the "newNameArray.length / 2" logic will work for both even and odd word lengths.

Also, I strongly advise not to use single letter variable names - who can tell what n, x and y are supposed to represent?
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
sorry for the confusion which really is, i changed the code to be as following but every word now is a palindrome even if it isn't. x is supposed to be half of the word length and when it reach one, the comparisons will start then, here is the code
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Seems to work fine for palindromes, but it runs into a stack overflow otherwise.

Consider this: what happens if x==1, but the characters are not equal?
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i changed the code according to your answer and it become as following but if i have any two similar characters it give me true like word
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And I don't think the "x" parameter works correctly, or is even necessary.

The condition to terminate the recursion should be if from==to (for odd word lengths) or from==to+1 (for even word length).


(Deleted because of your most recent post.)
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"from > to" seems the wrong condition; from==to-1 probably.

And what if from==to (for odd word lengths) ?
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i made the following change like the following but if the word have two similar letters it is considered to be palindrome like word "radars" is a palindrome
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thank you for your help, for even words the condition of (from == to-1) works fine and now i am searching for the odd words.
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That looks like it would only work with odd word lengths - for even length words from==to will never be true.
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i found another mistake in my code that it only checks for the most inner two letters and if they are the same it return true other wise it return false without taking care of the other letters in the word, you have been so patient with me.
 
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

i found another mistake in my code that it only checks for the most inner two letters and if they are the same it return true other wise it return false without taking care of the other letters in the word



I suggest you write down your recursion logic in text first. You're doing good with the program but sometimes if we write down things clearly, it helps up spot all our mistakes.

A thing about recursive algorithms is -
With recursion, we have one or more base cases that are defined non-recursively in terms of fixed quantities. Those are the cases that unwind the recursive call stack.

For example, for a factorial function, we can say that.

factorial(n) = 1 if n =0. ( This is the base case ).
= n*factorial(n-1) if n>= 1


Do you see a similar pattern in your problem statement?

In your case, if you reach the base case, you've found your palindrome. But the question is what is your base case.

Do you see that with every recursive call you are comparing values that are equidistant from the starting position and the ending position. starting position is 0. Ending position is the length of the array.. Again fixed things.
If the number is not a palindrome, you could break from all the recursive calls even before you reach the base case.
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is it an assignment or something that says that you have to use recursion for this problem statement?
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm probably overlooking something but these recursive calls are so unrelated.
I mean why should we use recursion for finding whether a String is a palindrome.
In your case, one invocation of the method does not affect the other. I
think recursion might be a bad choice for this problem statement cause your method
needs to return a boolean . Im hoping that if I'm wrong, someone out there might be willing to correct me.
 
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Recursion is just fine for this problem. The return type is not of importance at all when determining whether recursion is a suitable solution.

I prefer to use recursion over iteration when you can easily define a problem in terms of itself. A palindrome is a word where its first and last characters are equal, and the rest of the word is also a palindrome. See? I just defined a palindrome in terms of itself, so recursion is very useful in solving the problem.
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In pseudocode:
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Stephen. I've actually listed similar steps in my first response. Just I got confused cause the calls were returning a boolean. Just in my steps, I'm passing the same char array and the position from the starting position as the argument ( it would also be the position from the length of the array ).
 
Mohamad Samy
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
finally i found the solution for all even words as following:
again thank for all who replies for my post
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Heena Agarwal wrote:Thanks Stephen. I've actually listed similar steps in my first response. Just I got confused cause the calls were returning a boolean. Just in my steps, I'm passing the same char array and the position from the starting position as the argument ( it would also be the position from the length of the array ).


Which is fine; so just convert Stephan's pseudo-code:
Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mohamad Samy wrote:finally i found the solution for all even words as following:


It may work, but it's not optimal. Have a look at Stephan's pseudocode again, and try and work out why he wrote it that way.

Winston
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks, Winston.
 
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello.
When i think about recursion it always comes to mind as something that will save "space" for me. I am extremely lazy and i want to type as little code as possible.
For a string to be a palindrome first and last letter must be the same, and then when you remove those two letters the string that remains must also have first and second letter that match, and so on....Until there is no more letters that can form a string or there is one "middle" letter. DOod, d = d > O = o, DOxOD > D = D O = O, x no need to compare since it is in the middle.
Also string is already and array of characters.

I am quite stubborn at times, to the point that i do not know when to stop and think about the problem at hand, but rather trying to brute-force it. The kind people on the java ranch are more than kind enough to point people in the right direction, but also they constantly remind us newbies about the importance of keeping a cold head and taking a step back and thinking about the problem. Also basics are very important.

When i think about programing i imagine a martial arts designed for working out my brain, and others(the people who usually post responses, who are more knowledgeable than me i view as master lvl, for example
Heena Agarwal, Stephan van Hulst would be an instructor at such a place roundhouse kicking explaining recursion), and to be that good i always thought that they must really work on their basics like strengthening their joins and muscle (understanding Strings,Arrays,primitive data types and loops), and then move to the more advance stuff like roundhouse kicks(recursion).
 
Sheriff
Posts: 28365
99
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

S. Freeman wrote:When i think about recursion it always comes to mind as something that will save "space" for me. I am extremely lazy and i want to type as little code as possible.



Made me laugh. I remember writing a recursive method to remove leading zeroes from a string. Sure, there's lots of other ways I could have done it, but the recursive way was just fine. Didn't take long to write, it worked with no problems, and since the strings were only a few characters long I didn't have to fret over whether the other ways were more efficient. So yeah, you're right. Being lazy is important when you're a programmer.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

S. Freeman wrote:When i think about recursion it always comes to mind as something that will save "space" for me.


When I think about it, brain damage always comes to mind. Specifically:
...and if your head explodes with dark forebodings too
I'll see you on the dark side of the moon.


As someone wise once said:
"To understand recursion, you must first understand recursion."

Winston
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just don't know why ... but it seems like if our implementation is using recursion according to Stephan's definition and the implementation aligns exactly with it, recursion here is a good fit.

But if we are converting the String to a char array and then passing that char array ( or even if it is the same String ) and the displacement from starting position as a method argument and designing our recursive strategy accordingly, it does seem like it's iteration retrofitted to use recursion. Do you all also think that for this latter case also recursion is a better choice than iteration? I would have probably used simple iteration for this. But I know I might be wrong.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Heena Agarwal wrote:Do you all also think that for this latter case also recursion is a better choice than iteration? I would have probably used simple iteration for this. But I know I might be wrong.


I think what Stephan was saying was that if a problem can be defined in terms of itself, then it's a candidate for recursion (because the code is likely to be compact and easy to understand). However, there are several other factors that affect the choice, just two of which are:
  • The allowed stack depth. Unlike a linear procedure, there's a limit to the number of times a method can call itself (I think its normally around 64K, but I could well be wrong; on older machines it was often as low as 63, and 127 (Byte.MAX_VALUE) was a very common limit). Exceeding this value is when you get StackOverflowError's.
  • Memory - each recursive call involves a new stack frame which, while unlikely to trouble a modern machine in terms of size, still has to be allocated.
  • which is why I generally add at least one more condition when I'm considering recursion:
    Does the recursive call decrease the size of the problem exponentially?

    I believe it's also called the "divide and conquer" rule. Quicksort is a classic case in point: Each call halves the problem in size, so even for a file containing a billion records, the maximum call depth will only be about 30.

    The palindrome solution, on the other hand, only reduces the problem by 2, so for a String of size n, the maximum call depth will be n/2. It's therefore easy to imagine a String that could cause a StackOverflowError.

    HIH

    Winston
     
    Heena Agarwal
    Ranch Hand
    Posts: 262
    4
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Thanks, Winston. You've confirmed my thoughts about when to use recursion.

    I have also used ( a few months back ) recursion in almost all my tree problems, and in a lot of my search and sort algorithms and yes I love to use recursion with quicksort cause more than anything, it simplifies the implementation for me. Quite a few times the algorithms that used iteration were way too complex ( or so the ones I have worked on appeared to me ) for me. I have always liked and preferred easy and simple things to the complex ones.

    However with the palindrome problem (even if we ignore for the time being the long Strings ), even the complexity remained almost the same. It seemed like with every stack frame the String size reduced, but with every iteration also it would have reduced equally. So there was no added advantage of using recursion in the case of the palindrome problem.

    Also if the approach is to pass the displacement from the starting position to the recursive implementation, I find it difficult to even visualize the problem with recursion.

     
    Winston Gutkowski
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Heena Agarwal wrote:However with the palindrome problem (even if we ignore for the time being the long Strings ), even the complexity remained almost the same. It seemed like with every stack frame the String size reduced, but with every iteration also it would have reduced equally. So there was no added advantage of using recursion in the case of the palindrome problem.


    Well spotted. Another thing I remember being taught (many years ago ) is that ANY problem that has a recursive solution can also be solved with linear code (usually involving stacks, but not always), so the question you need to ask yourself is: Is the linear solution a lot more complex than the recursive one?

    If not, the chances are that recursion isn't a big help.

    Winston
     
    Heena Agarwal
    Ranch Hand
    Posts: 262
    4
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Thank you, Winston. I shall keep these points in mind.
     
    Winston Gutkowski
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Heena Agarwal wrote:Thank you, Winston. I shall keep these points in mind.


    You're most welcome. Glad we could help.

    Winston
     
    Marshal
    Posts: 80226
    424
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Winston Gutkowski wrote: . . . I remember being taught (many years ago ) . . .

    I remember being taught, not quite that many years ago (2009) that recursion was invented before iteration, but you can use (for example) Dijkstra's weakest precondition transformer semantics to prove that recursion and iteration are equivalent to each other.
     
    Winston Gutkowski
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:I remember being taught...that recursion was invented before iteration, but you can use (for example) Dijkstra's weakest precondition transformer semantics to prove that recursion and iteration are equivalent to each other.


    Providing, of course, you remember what 'Dijkstra's weakest precondition transformer semantics' are. I kind of get it from the name; but it's not simple stuff (I refer you back to my Pink Floyd post).

    Winston
     
    Campbell Ritchie
    Marshal
    Posts: 80226
    424
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    WP semantics is really easy to understand, until you get to iteration and recursion
    while(g) do S end[Q] = (S = μ (g → S ; S))[Q]
    Using μ for least common bound permits an infinite loop, which doesn't have a least common bound, to degenerate to abort.h

    At least I think that is the correct WP effect. You can see that you are either doing S and calling S, or you are doing S and repeating S. Both have the same WP effect.
     
    Stephan van Hulst
    Bartender
    Posts: 15737
    368
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Note that you *probably* don't have to worry about stack overflows if your recursive calls happen at an exit point of the method.

    If you perform return isPalindrome(s.substring(1, s.length()-1)) the compiler is likely to pop the current frame off the stack before it pushes the next frame on. It's called tail-recursion, and I *think* that in javac it was implemented in 1.6.
     
    Heena Agarwal
    Ranch Hand
    Posts: 262
    4
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:Note that you *probably* don't have to worry about stack overflows if your recursive calls happen at an exit point of the method.

    If you perform return isPalindrome(s.substring(1, s.length()-1)) the compiler is likely to pop the current frame off the stack before it pushes the next frame on. It's called tail-recursion, and I *think* that in javac it was implemented in 1.6.



    Wow. I didn't know about this. Interesting. Thank you...
     
    Paul Clapham
    Sheriff
    Posts: 28365
    99
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I did some googling and I found that the industry standard term is "tail call optimization". I also didn't find anything that said Java supported it, either in the compiler or the JIT at run time. And the existence of stack overflow exceptions (see many questions in this forum) suggests to me that it isn't supported.

    Of course if it was, it would only convert all of those naive recursion errors from stack overflows to infinite loops...
     
    Heena Agarwal
    Ranch Hand
    Posts: 262
    4
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I should have googled it. Stephan indicated he wasn't sure if this was implemented in JDK 1.6. I didn't even google it. Sorry about that. Thanks for the right term, Paul.

    Nevertheless this optimization does seem interesting. It seems scala supports recursion tail call optimizations but Java doesn't support it.

    Here is what I found in the OpenJDKWiki-- https://wiki.openjdk.java.net/display/mlvm/TailCalls.

    Not sure if this is work in progress for JDK 1.8 but I'll read about it in the weekend.



     
    Stephan van Hulst
    Bartender
    Posts: 15737
    368
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Huh, I guess I completely misread or misremembered it then.

    Good thing I never really depended on it
     
    Author
    Posts: 587
    6
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    In regards to Palindromes, here are some other cool things that can be done with alphabetics in the space of wordplay:

    http://robertjliguori.blogspot.com/2014/02/fun-with-alphabetics.html

    It would actually be pretty cool if a library / API was created to support all of these topics.

    Perhaps it could be called the Logology API. Someone want to set it up as an opensource project?

    -- Robert
     
    rubbery bacon. crispy tiny ad:
    Smokeless wood heat with a rocket mass heater
    https://woodheat.net
    reply
      Bookmark Topic Watch Topic
    • New Topic