Learn how to a build a cloud-first strategyRegister Now

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 1111

# 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) & " "
Next

Dim answ As Integer = Palindrome(charArray)
If answ = 1 Then
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
0
Zaurb
• 9
• 4
• 2
1 Solution

Commented:
A recursive function calls itself unless it has reached a state where the recursion is no longer possible or necessary.

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

0

Author Commented:
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?
0

Commented:
What is the line before this bit?
0

Author Commented:
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

0

Commented:
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
0

Commented:
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.
0

Commented:
Sorry, the post above wasn't there a moment ago.
0

Commented:
Plus i think Zaurb is interested in recursion
0

Author Commented:
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.

0

Commented:
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(last))) 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
0

Commented:
This is a lazy way of showing you the structure. Its best not to start passing string about too much.
0

Commented:

Function Palindrome(ByRef word As String) As Integer
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(last))) 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
0

Commented:
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
0

Commented:
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!!
0

Author Commented:
<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!

0

## Featured Post

• 9
• 4
• 2
Tackle projects and never again get stuck behind a technical roadblock.