Win a copy of Java Database Connections & Transactions (e-book only) this week in the JDBC forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Knute Snortum
  • Paul Clapham
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Frits Walraven
Bartenders:
  • Ganesh Patekar
  • Tim Holloway
  • salvin francis

Recursive method  RSS feed

 
Greenhorn
Posts: 12
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello. I am trying to solve a following problem : Write a recursive function that determines whether an array is a palindrome, where the array and its size are given as parameters. The method returns 1 if a[] is a palindrome, 0 otherwise. The exercise comes from : http://www.bowdoin.edu/~ltoma/teaching/cs107/spring05/recursion.html

I've got a solution that seems to work,but since recursion is difficult to me and I am self-studying, it would be great to get some feedback on it. Here it is :




 
Bartender
Posts: 5854
57
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You also need to clean up your indentation.
 
Carey Brown
Bartender
Posts: 5854
57
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You only need to test half the characters against the other half. No need to count from length N to zero.
 
Marshal
Posts: 64496
225
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I it works, it can't be that bad, but, don't use ints instead of booleans. Try the following inputIt is slightly odd the way that your exercise requires the length of the array, because every array has a field called length, Maybe the exercise is intended to be solved in C, not Java®, because:-
  • 1: The [] are written later than would be correct style in Java®.
  • 2: The size of the array would be required in C, but isn't in Java®.
  • 3: Java® has a boolean type, but C doesn't and has to use int.
  • The method names aren't correct style for either language: in C they would read is_palindrome() and in Java® isPalindrome(). Don't call classes things like MyClass or C1. Give them informative names.
    So let's try the method according to Java® conventions:-Note I have called the second parameter pairLocation because it doesn't determine the size of the array, but which pair of letters you are comparing. You are right to use the subtractions, but you need to work out where to stop. There is no need to go back to pairLocation = 0.
    What are the criteria for being a palindrome:-
  • 1: A String with one letter or less is a palindrome.
  • 2: A String is a palindrome if its first and last letters are the same, and the remainder with those two letters taken off is a palindrome.
  • Use the :? operator or a singlle expression if possible.Your lines 24‑26 are nearly as incorrect as the last code block I showed you. Look at our style suggestions whch will give you a hint about what is wrong.
     
    Bartender
    Posts: 2287
    95
    Eclipse IDE Google Web Toolkit Java
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Recursively, my mind thinks in the following way :
     
    Marshal
    Posts: 5999
    156
    Chrome Eclipse IDE Java Postgres Database Ubuntu VI Editor
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    And keep in mind that it has to work on palindromes such as "redder" that have an even number of letters.
     
    Campbell Ritchie
    Marshal
    Posts: 64496
    225
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    OP: What progress have you made. Did you find out what happens if you use new char[]{'c', 'h', 'r', 'o', 'n', 'i', 'c'} as input?
     
    Dawid Smith
    Greenhorn
    Posts: 12
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you guys for all the suggestions. Also, I am very sorry to reply so late. I hope it won't look like I don't appreciate your help but sometimes real life gets in a way big time. Anyways, getting back to the problem. I attempted to correct the recursive method. Here it is :




    I would love to hear your opinions
     
    salvin francis
    Bartender
    Posts: 2287
    95
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Have a cow for sharing your implementation with us.
    Typically, I would have suggested comparing the index for equality first since if both indexes are same, then the comparison is not needed. However, I see that doing this wont achieve much difference.
    I think that your implementation is good given the constraints of the problem specified. Ideally, I would suggest not calculating "ar.length/2" for every iteration since it does not change. A more simpler implementation would be to send a cropped copy of the array to the next recursive call instead of the pairLocation.
     
    salvin francis
    Bartender
    Posts: 2287
    95
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    [Nitpick on]
    The original question asks you to write:
    whereas your definition is:The method does not spell the same and the return type does not match
    [Nitpick off]
     
    Marshal
    Posts: 24506
    55
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    salvin francis wrote:The original question asks you to write: ...



    Yes, the original post said

    The method returns 1 if a[] is a palindrome, 0 otherwise.


    But that's an icky design for Java, it looks like somebody was used to writing C and didn't know much Java. So I'd fully support returning a boolean value.
     
    Dawid Smith
    Greenhorn
    Posts: 12
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Paul Clapham wrote:

    salvin francis wrote:The original question asks you to write: ...



    Yes, the original post said

    The method returns 1 if a[] is a palindrome, 0 otherwise.


    But that's an icky design for Java, it looks like somebody was used to writing C and didn't know much Java. So I'd fully support returning a boolean value.



    I forgot to mention that I intentionally made a change to boolean type following Campbell Ritchie's suggestion. He suspected that the exercise isn't intended to be solved in Java because of the required parameters. It turned out that he was correct. My bad for choosing wrong source for the exercises.
     
    salvin francis
    Bartender
    Posts: 2287
    95
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Paul Clapham wrote:But that's an icky design for Java, it looks like somebody was used to writing C and didn't know much Java.


    Yes, I too agree on the ickiness
     
    Dawid Smith
    Greenhorn
    Posts: 12
    1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    salvin francis wrote:Have a cow for sharing your implementation with us.
    Typically, I would have suggested comparing the index for equality first since if both indexes are same, then the comparison is not needed. However, I see that doing this wont achieve much difference.
    I think that your implementation is good given the constraints of the problem specified. Ideally, I would suggest not calculating "ar.length/2" for every iteration since it does not change. A more simpler implementation would be to send a cropped copy of the array to the next recursive call instead of the pairLocation.



    Thank you for the feedback and the Cow. I didn't know it was a thing. I am going to try to modify the code according to your advice.

    In the meantime, how would you guys go about testing such a method? I have 0 experience in this and previously linked "Evil Unit Testing" by Paul Wheaton seems too advanced for me now. Therefore, I attempted to write a program that would test isPalindrom() method before posting it. What it does is :
    1)Generates random char array. The method allows us to decide how many char primitives will the array have as well as what range of ASCII characters will be used to create those arrays. I thought it would be useful for testing since repetition of char primitives is relevant to determine whether something is palindrom or not and that feature allows us to choose narrow range of ASCII characters to make repetition more frequent if desired.
    2)Generates 2d array consisting of desired number of previosly generated random char arrays.

    Here is the full code that includes isPalindrom method and the testing methods :



    Do you think it's acceptable way of testing this method?
     
    Saloon Keeper
    Posts: 3256
    128
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    hi Dawid,

    If you want to pass these assignments, stick to the specification and return an int.

    Your method looks alright to me (haven't tested it yet), but your interpretation is confusing, as is mentioned already. The original assignment talks about a method isPalindrom(char[] array, int size), where the second parameter is the (for java superfluous) size of the array. Your current method has this second parameter as an index. When starting, both arguments are equal, but in the following recursion, the arraylength involved is decreased by 2, and your index only by 1.

    The easy way out is already suggested: in your recursion, send the array as argument, stripped from its first and last element. The Arrays class has a very suitable method for this: have a look at the API of Arrays.

    About your testing: in principle okay, but I would have used some fixed arrays of which I know upfront whether they are palindrome or not. Now you must manually check the outcomes! Okay, your arrays are only 4 long, and 10 in total, so doable, but beware! The chance that an array is a palindrom is only 1 / 16 (according to your method), so don't be surprised if your 2d testarray contains no palindrome at all!
     
    salvin francis
    Bartender
    Posts: 2287
    95
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    palindrome
     
    salvin francis
    Bartender
    Posts: 2287
    95
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I did a quick search on wiki and found Palindrome :

    Palindromes often consist of a sentence or phrase, e.g., "Mr. Owl ate my metal worm", "Do geese see God?", "Was it a car or a cat I saw?", "Murder for a jar of red rum" or "Go hang a salami, I'm a lasagna hog". Punctuation, capitalization, and spaces are usually ignored. Some, such as "Rats live on no evil star", "Live on time, emit no evil", and "Step on no pets", include the spaces.

     
    Let's get him boys! We'll make him read this tiny ad!
    how do I do my own kindle-like thing - without amazon
    https://coderanch.com/t/711421/engineering/kindle-amazon
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!