Learn how to a build a cloud-first strategyRegister Now

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

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
0
Zaurb
Asked:
Zaurb
  • 9
  • 4
  • 2
1 Solution
 
Babycorn-StarfishCommented:
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

This may be a bit hazy, feel free to ask for more info :)
0
 
ZaurbAuthor 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
 
Babycorn-StarfishCommented:
What is the line before this bit?
0
Fill in the form and get your FREE NFR key NOW!

Veeam is happy to provide a FREE NFR server license to certified engineers, trainers, and bloggers.  It allows for the non‑production use of Veeam Agent for Microsoft Windows. This license is valid for five workstations and two servers.

 
ZaurbAuthor 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
 
DarrenDCommented:
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
 
Babycorn-StarfishCommented:
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
 
Babycorn-StarfishCommented:
Sorry, the post above wasn't there a moment ago.
0
 
Babycorn-StarfishCommented:
Plus i think Zaurb is interested in recursion
0
 
ZaurbAuthor 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
 
Babycorn-StarfishCommented:
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
 
Babycorn-StarfishCommented:
This is a lazy way of showing you the structure. Its best not to start passing string about too much.
0
 
Babycorn-StarfishCommented:
sorry missed the header

    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
 
DarrenDCommented:
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
 
Babycorn-StarfishCommented:
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
 
ZaurbAuthor 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

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

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