Zaurb
asked on
Palindrome Exercise on recursion.
Hi!
I'm learning VB.NET and do exercises from Deitel. There's on on recursions and arrays which I can't really understand. Some examples which I've found in the book and also in internet for recursions all are abot factorials. I read all of them 10 times and still can't get the recursion working.... Extremely frustrating... The exercise I'm doing right now is as follows:
-------------------------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- --------
(Palindromes) A palindrome is a String that is spelled the same forward and backward.
Some examples of palindromes are: radar, able was i ere i saw elba and, if blanks are ignored, a
man a plan a canal panama. Write a recursive procedure TestPalindrome that returns True if
the String stored in the array is a palindrome, but False otherwise. The procedure should ignore
spaces and punctuation in the String. [Hint: A String can be converted to a Char array using
method ToCharArray. For instance, the statement
myArray = myString.ToCharArray()
stores the contents of string variable myString in a one-dimensional Char array myArray.]
-------------------------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- --------
All I could do til now was a code below which doesn't employ any recursion and even doesn't work well. What am I doing wrong? How do I use recursion here? Please HELP.
Public Class Form1
Private Sub btnCheck_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCheck.Click
Dim charArray As Char() = New Char() {}
Dim userText As String = txtString.Text
Dim answer As String = ""
Dim i As Integer = 0
charArray = userText.ToCharArray()
For i = 0 To charArray.GetUpperBound(0)
answer &= charArray(i) & " "
lblAnswer.Text = answer
Next
Dim answ As Integer = Palindrome(charArray)
If answ = 1 Then
lblAnswer.Text &= vbCrLf & "Palindrome"
Else
lblAnswer.Text &= vbCrLf & "NOT Palindrome"
End If
End Sub
Function Palindrome(ByVal charArray As Char()) As Integer
Dim first As Integer = 0
Dim last As Integer = charArray.GetUpperBound(0)
For first = 0 To charArray.GetUpperBound(0)
For last = charArray.GetUpperBound(0) To 0
If charArray(first) = charArray(last) Then
Return 1
Else
Return 0
End If
Next last
Next first
End Function
I'm learning VB.NET and do exercises from Deitel. There's on on recursions and arrays which I can't really understand. Some examples which I've found in the book and also in internet for recursions all are abot factorials. I read all of them 10 times and still can't get the recursion working.... Extremely frustrating... The exercise I'm doing right now is as follows:
--------------------------
(Palindromes) A palindrome is a String that is spelled the same forward and backward.
Some examples of palindromes are: radar, able was i ere i saw elba and, if blanks are ignored, a
man a plan a canal panama. Write a recursive procedure TestPalindrome that returns True if
the String stored in the array is a palindrome, but False otherwise. The procedure should ignore
spaces and punctuation in the String. [Hint: A String can be converted to a Char array using
method ToCharArray. For instance, the statement
myArray = myString.ToCharArray()
stores the contents of string variable myString in a one-dimensional Char array myArray.]
--------------------------
All I could do til now was a code below which doesn't employ any recursion and even doesn't work well. What am I doing wrong? How do I use recursion here? Please HELP.
Public Class Form1
Private Sub btnCheck_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCheck.Click
Dim charArray As Char() = New Char() {}
Dim userText As String = txtString.Text
Dim answer As String = ""
Dim i As Integer = 0
charArray = userText.ToCharArray()
For i = 0 To charArray.GetUpperBound(0)
answer &= charArray(i) & " "
lblAnswer.Text = answer
Next
Dim answ As Integer = Palindrome(charArray)
If answ = 1 Then
lblAnswer.Text &= vbCrLf & "Palindrome"
Else
lblAnswer.Text &= vbCrLf & "NOT Palindrome"
End If
End Sub
Function Palindrome(ByVal charArray As Char()) As Integer
Dim first As Integer = 0
Dim last As Integer = charArray.GetUpperBound(0)
For first = 0 To charArray.GetUpperBound(0)
For last = charArray.GetUpperBound(0)
If charArray(first) = charArray(last) Then
Return 1
Else
Return 0
End If
Next last
Next first
End Function
ASKER
Thank you!
Another problem is that debugger steps over the following part of the code:
For last = charArray.GetUpperBound(0) To 0
If charArray(first) = charArray(last) Then
last -= 1
Palindrome(charArray)
Else
Return (0)
End If
Next last
It doesn't even eter this part. Why?
Another problem is that debugger steps over the following part of the code:
For last = charArray.GetUpperBound(0)
If charArray(first) = charArray(last) Then
last -= 1
Palindrome(charArray)
Else
Return (0)
End If
Next last
It doesn't even eter this part. Why?
What is the line before this bit?
ASKER
I've modified the above code:
Function Palindrome(ByVal charArray As Char()) As Integer
Dim first As Integer = 0
Dim last As Integer = charArray.GetUpperBound(0)
If charArray.Length <> 0 Then
For first = 0 To charArray.GetUpperBound(0)
For last = charArray.GetUpperBound(0) To 0
If charArray(first) = charArray(last) Then
last -= 1
Palindrome(charArray)
Else
Return (0)
End If
Next last
Next first
Else
MessageBox.Show("Empty String!", "Warning!", MessageBoxButtons.OK, MessageBoxIcon.Warning)
End If
End Function
Function Palindrome(ByVal charArray As Char()) As Integer
Dim first As Integer = 0
Dim last As Integer = charArray.GetUpperBound(0)
If charArray.Length <> 0 Then
For first = 0 To charArray.GetUpperBound(0)
For last = charArray.GetUpperBound(0)
If charArray(first) = charArray(last) Then
last -= 1
Palindrome(charArray)
Else
Return (0)
End If
Next last
Next first
Else
MessageBox.Show("Empty String!", "Warning!", MessageBoxButtons.OK, MessageBoxIcon.Warning)
End If
End Function
Hi,
I've not done anything on recursion but you can perform the check without two 'For' loops
Function Palindrome(ByVal charArray As Char()) As Integer
Dim first As Integer = 0
Dim last As Integer = charArray.GetUpperBound(0)
Dim IsPalindrome As Boolean = False
If charArray.Length <> 0 Then
' You only need one loop, with an extra bit to divide it by two.
For first = 0 To charArray.GetUpperBound(0) / 2
If charArray(first) = charArray(last - first) Then
IsPalindrome = True
Else
' If two of the chars do not match then straight away you know its not a palindrome.
Return False
End If
Next first
End If
Return IsPalindrome
End Function
I've also removed the spaces in the original string as well
' This removes all the spaces. You can do the same for punctuation.
' You could write some code to jump over a space if it finds one but I just got rid of all the spaces.
userText = userText.Replace(" ", "")
Cheers,
Darren
I've not done anything on recursion but you can perform the check without two 'For' loops
Function Palindrome(ByVal charArray As Char()) As Integer
Dim first As Integer = 0
Dim last As Integer = charArray.GetUpperBound(0)
Dim IsPalindrome As Boolean = False
If charArray.Length <> 0 Then
' You only need one loop, with an extra bit to divide it by two.
For first = 0 To charArray.GetUpperBound(0)
If charArray(first) = charArray(last - first) Then
IsPalindrome = True
Else
' If two of the chars do not match then straight away you know its not a palindrome.
Return False
End If
Next first
End If
Return IsPalindrome
End Function
I've also removed the spaces in the original string as well
' This removes all the spaces. You can do the same for punctuation.
' You could write some code to jump over a space if it finds one but I just got rid of all the spaces.
userText = userText.Replace(" ", "")
Cheers,
Darren
Hmmm,
it's recursive but it's not the best way of doing it.
You don't need either of the for loops, just check the first and last letters, if they are fine (identical) you make an array from the bits between the first and last indices, try writing a word down on a piece of paper drawing boxes around the first and last letters, you now need to make an array from everything which doens't have a box around it. You then pass in this new array (lets call it newArray) to Palindrome.
The idea is that you're breaking down the problem into smaller chunks and the checking stops the process at any time where there aren't matching letters or the process runs to completion.
it's recursive but it's not the best way of doing it.
You don't need either of the for loops, just check the first and last letters, if they are fine (identical) you make an array from the bits between the first and last indices, try writing a word down on a piece of paper drawing boxes around the first and last letters, you now need to make an array from everything which doens't have a box around it. You then pass in this new array (lets call it newArray) to Palindrome.
The idea is that you're breaking down the problem into smaller chunks and the checking stops the process at any time where there aren't matching letters or the process runs to completion.
Sorry, the post above wasn't there a moment ago.
Plus i think Zaurb is interested in recursion
ASKER
Thanks Babycorn-Starfish!
I feel I get the better idea of what I have to do now. I will post a code in a few minutes as soon as I finish writing it.
I feel I get the better idea of what I have to do now. I will post a code in a few minutes as soon as I finish writing it.
Okay, dont look at this then!!!
If (word Is Nothing Or word = String.Empty) Then
Return -1
End If
Dim first As Integer = 0
Dim last As Integer = word.Length - 1
If (first = last) Then 'could be the middle
Return 1
End If
If (word(first).Equals(word(l ast))) Then
If (word.Length = 2) Then
Return 1
End If
Return Palindrome(word.Substring( first + 1, last - 1))
Else
Return 0
End If
End Function
If (word Is Nothing Or word = String.Empty) Then
Return -1
End If
Dim first As Integer = 0
Dim last As Integer = word.Length - 1
If (first = last) Then 'could be the middle
Return 1
End If
If (word(first).Equals(word(l
If (word.Length = 2) Then
Return 1
End If
Return Palindrome(word.Substring(
Else
Return 0
End If
End Function
This is a lazy way of showing you the structure. Its best not to start passing string about too much.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi,
Zaurb - I know that you are interested in recursion. But I just want to make sure that you know recursion may not be the best solution for this type of problem as you are making many function calls when you don't need to. It's a whole lot slower performing recursion and would not be useful in the real world.
I know the factorial one's are maybe a bit more difficult but they get the point of recursion accross alot better.
Cheers,
Darren
Zaurb - I know that you are interested in recursion. But I just want to make sure that you know recursion may not be the best solution for this type of problem as you are making many function calls when you don't need to. It's a whole lot slower performing recursion and would not be useful in the real world.
I know the factorial one's are maybe a bit more difficult but they get the point of recursion accross alot better.
Cheers,
Darren
right, do you understand how/why it works? I've no problem explaining it so you know you understand it fully - it's not just the code!!
ASKER
<b>To: DarrenD</b>
Thank you for your answer! I quite agree that in some cases, maybe this one as well, recursion is not the best solution. It fills up the memory very quickly, etc. But the reason I need a recursion approach here is that I'm trying to learn VB with Deitel's How To Program Visual Basic .NET and this exercise was accented on recursion approach.
<b>To: Babycorn-Starfish</b>
I really appreciate your help! I looked through your code but now I will spend some more minutes to understand it better. If I need further clarifications I will ask you for an assistance. Thank you very much!
Thank you for your answer! I quite agree that in some cases, maybe this one as well, recursion is not the best solution. It fills up the memory very quickly, etc. But the reason I need a recursion approach here is that I'm trying to learn VB with Deitel's How To Program Visual Basic .NET and this exercise was accented on recursion approach.
<b>To: Babycorn-Starfish</b>
I really appreciate your help! I looked through your code but now I will spend some more minutes to understand it better. If I need further clarifications I will ask you for an assistance. Thank you very much!
The way you have it set up uses repetition via a for..loop.
I'm sure someone else will explain it better but In a nutshell, to bring about the recursion you'd need to
- Pass in the charArray
- Check charArray isn't empty or null- error state
- Get first and last indices as you have done
- if char at first index = char at last index then this bit satisfies the palindrome rule so
-if there are more characters to process pass the charArray segment between the first and last indices back into the function, it'll seem odd but just call the function again from inside the function passing in the smaller charArray
- else return 1 coz you've processed it all and there's no more to process
- else not a palindrome so return 0
This may be a bit hazy, feel free to ask for more info :)