Solved

# Palindrome Exercise on recursion.

Posted on 2007-07-26
942 Views
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
Question by:Zaurb

LVL 11

Expert Comment

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

LVL 1

Author Comment

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

LVL 11

Expert Comment

What is the line before this bit?
0

LVL 1

Author Comment

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

LVL 18

Expert Comment

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

LVL 11

Expert Comment

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

LVL 11

Expert Comment

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

LVL 11

Expert Comment

Plus i think Zaurb is interested in recursion
0

LVL 1

Author Comment

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

LVL 11

Expert Comment

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

LVL 11

Expert Comment

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

LVL 11

Accepted Solution

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

LVL 18

Expert Comment

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

LVL 11

Expert Comment

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

LVL 1

Author Comment

<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

More often than not, we developers are confronted with a need: a need to make some kind of magic happen via code. Whether it is for a client, for the boss, or for our own personal projects, the need must be satisfied. Most of the time, the Framework…
Today I had a very interesting conundrum that had to get solved quickly. Needless to say, it wasn't resolved quickly because when we needed it we were very rushed, but as soon as the conference call was over and I took a step back I saw the correct …
Migrating to Microsoft Office 365 is becoming increasingly popular for organizations both large and small. If you have made the leap to Microsoft’s cloud platform, you know that you will need to create a corporate email signature for your Office 365…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…