Thread: Recursion Revisited again, and again!

  1. #1
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164

    Recursion Revisited again, and again!

    This is just so frustrating for me. I finished the chapter on recursion and thought, wrongly, that I was finished with recursion. Well, I am not. I am rewriting a sequential seach function of an array-based list class as an ADT. I understand that I have to find the base case(s), and taking the original function and calling it again with a smaller range of elements from the list. I think I have successfully done that with what I have written, but won't know until I can find the final piece which is making the list smaller.

    The class has private members of a list pointer (elem Type *list), length and maxSize. The function accepts a reference to item as its argument. So, that is all I can include in the recursive call to the function, so HOW do I get the list one element smaller in the recursive call??? Recursion will be the death of me in programming.


    My code is:
    Code:
    template <class elemType>
    int arrayListType<elemType>::seqSearch(const elemType& item)
    {
    	int loc;
    	if (length == 0 || loc == length)
    		return -1;
    	else if (list[loc] == item)
    		return loc;
    	else
    	{
    		return seqSearch(item);  //THIS IS MY PROBLEM STATEMENT - MENTAL BLOCK!!!
    	}
    
    } //end seqSearch
    Thanks for the help.

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    All I see is static code - it will loop forever like that.
    You need to make a condition so that it will break the recursion sometime.
    loc, length and list aren't updated or passed as arguments at all, so nothing is done at each recursion.

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    This may help.

    Code:
    template <class elemType>
    int arrayListType<elemType>::seqSearch(const elemType& item)
    {
       static int loc =0;
       loc++;
       //Assuming here that length and list are members
       if (length == 0 || loc == length)
       { 
          return -1;
       }
       else if (list[loc] == item)
       {  
         return loc;
       }   
       else
       {
         return seqSearch(item);  //THIS IS MY PROBLEM STATEMENT - MENTAL BLOCK!!!
       }
    
    } //end seqSearch
    Last edited by VirtualAce; 12-01-2007 at 01:52 PM.

  4. #4
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    BUBBA!!! You are awesome, That did it! I thought that I had to include some kind of recursive reduction of list in the seqSearch() return statement. I thought about initializing loc to 0, but then realized every time the function was called it would be reset to zero and THAT wasn't what I wanted. This is perfect!!! I haven't done a lot with static variable declarations/initializations, so this was a good thing in two directions.

    length and list are both private members. This seqSearch function is not private, but is used in other member functions, only.

    Thank you so, SO much!
    Last edited by clegs; 12-01-2007 at 02:09 PM.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by clegs View Post
    BUBBA!!! You are awesome, That did it!

    length and list are both private members. This seqSearch function is not private, but is used in other member functions, only.

    Thank you so, SO much!
    So, if it's NOT used by anything outside the class itself (e.g only in member functions), it SHOULD be private!

    And if we assume that the compiler actually makes this into a recursive function, it's noticably less efficient just using a for/while loop to search in the list, and the static variable makes it non-reentrant, so if you have multiple instances of the class, you can't do a search in one and a search in another. Actually, I also think you need to find a way to reset the loc variable to zero when you do the first search.

    Perhaps the following is a better implementation, if you insist on using recursion:
    Code:
    template <class elemType>
    int arrayListType<elemType>::seqSearch(const elemType& item, int loc = 0)
    {
       //Assuming here that length and list are members
       if (length == 0 || loc == length)
       { 
          return -1;
       }
       else if (list[loc] == item)
       {  
         return loc;
       }   
       else
       {
         return seqSearch(item, loc+1);  //THIS IS MY PROBLEM STATEMENT - MENTAL BLOCK!!!
       }
       
    }
    A slightly neater solution, but requiring adding another member function, would be to have one function seqSearch that calls a helper function that is the actual search, seqSearchImpl(item, loc), avoiding the possibility of some programmer deciding to pass a loc value into the function - this helper function should DEFINITELY be a private function, to avoid misuse of the function.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by matsp View Post
    So, if it's NOT used by anything outside the class itself (e.g only in member functions), it SHOULD be private!
    That's kinda up to implementation. You should ask yourself if it SHOULD be used by anything outside the class, and if not it should be private (or protected if you want another class to inherit it through inheritance).

    Otherwise I agree with Matsp - this is better done with a simple loop. And if not a loop, matsp's other recursion solution is also better than your implentation.

  7. #7
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    The original code was an iterative loop to find the item, however, it is an assignment to rewrite the code as a recursive function. If it were up to me I'd keep it as an iterative search!

    The book didn't make it private which is what I checked when first reviewing the assignment. I expected it to be, but it wasn't.

    Thanks for the extra info on the code, I will modify it. I've only checked for two of the three possible circumstances, and it has functioned so far, but I haven't been exhaustive with my error checking yet.

    Is there anything else that may slip me up on this cursive recursive function??

    I appreciate all the dialog, and learn barrels from this forum.

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    And that's another bad thing - trying to turn all those iteration-functions into recursive ones. They shouldn't be. If someone is going to teach someone how to do a recursive function, then do it properly. There are only rare cases where recursion is needed.

  9. #9
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Thank GOD!!
    I hate thinking of how to rewrite an interative function that works JUST FINE into a recursive one.
    I have three assignments in this chapter and they are all rewriting interative loop functions into recursive functions. The chapter is on Search Algorithms. We've already covered Recursion 3 chapters back and used all the typical examples - factorials, tower of Hanoi, and Fibonacci number. Go figure!

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I feel your pain, clegs. But there isn't much we can do but endure

  11. #11
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Amen!

  12. #12
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    I was checking all my programs to make sure everything was working properly and all comments were inserted and accurate when...

    My recursive function seqSearch didn't work when called a second time within the same driver program. I came back to this thread and researched what was said. I tried my hand at the two options that Mats provided and I can't get either to work.

    The code I have now gives me an error at run time. The code I had before ran but the second function call said the number it was searching for wasn't in the list when it was and I think it is because 'loc' isn't getting reset to '0' when it enters the function the second time within the same run.

    Mats said:
    Perhaps the following is a better implementation, if you insist on using recursion:
    Code:
    template <class elemType>
    int arrayListType<elemType>::seqSearch(const elemType& item, int loc = 0)
    {
       //Assuming here that length and list are members
       if (length == 0 || loc == length)
       { 
          return -1;
       }
       else if (list[loc] == item)
       {  
         return loc;
       }   
       else
       {
         return seqSearch(item, loc+1);  //THIS IS MY PROBLEM STATEMENT - MENTAL BLOCK!!!
       }
       
    }
    A slightly neater solution, but requiring adding another member function, would be to have one function seqSearch that calls a helper function that is the actual search, seqSearchImpl(item, loc), avoiding the possibility of some programmer deciding to pass a loc value into the function - this helper function should DEFINITELY be a private function, to avoid misuse of the function.
    This code actually works but returns the wrong location in the list.
    And this is my current code, but I have eliminated a lot of code - class and member function definitions - that isn't related to this problem:
    Code:
    template <class elemType>
    class arrayListType
    {
    public:
        int seqSearch(const elemType& item);
      		//Function to search the list for a given item. 
    		//Postcondition: If the item is found, returns the location 
    		//               in the array where the item is found; 
       		//               otherwise, returns -1.
    protected:
        elemType *list; 	//array to hold the list elements
        int length;			//to store the length of the list
        int maxSize;		//to store the maximum size of the list
    private:
    	int seqSearchImpl(const elemType& item, int loc = 0);
    
    };
    
    template <class elemType>
    int arrayListType<elemType>::seqSearch(const elemType& item)
    {
    	int loc = 0;
    	seqSearchImpl(item, loc);
    	return loc;
    }
    
    template <class elemType>
    int arrayListType<elemType>::seqSearchImpl(const elemType& item, int loc)
    {
    	if (length == 0 || loc == length)
    		return -1;
    	else if (list[loc] == item)
    		return loc;
    	else
    	{
    		return seqSearchImpl(item, loc + 1);	//recursive call of seqSearch function
    	}
    
    } //end seqSearch
    And this is the part of the driver program that calls the function. I have the same code in the program for two lists.
    Code:
    //using the recursive seqSearch function
    	cout << "Enter a number to search for in the list: ";
    	int num;
    	cin >> num;
    	int check = intList.seqSearch(num);						//seqSearch Function call
    	if (check == -1)
    		cout << "The number you entered was not found in the list." << endl;
    	else
    		cout << "The number you entered is at location: " << check + 1
    			 << " in the list." << endl;
    Thank you for your time in helping me.

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by clegs View Post
    The code I had before ran but the second function call said the number it was searching for wasn't in the list when it was and I think it is because 'loc' isn't getting reset to '0' when it enters the function the second time within the same run.
    loc shouldn't be reset to 0 every time the function returns because loc is the position in the list that it checks. So if it was 0 every time, it would check index0 for the number and then index0, and so on in an endless loop.

    I believe the problem is that your search function RETUNS the number in the list where the item is in the list, but you're not returning it.

    Code:
    template <class elemType>
    int arrayListType<elemType>::seqSearchImpl(const elemType& item, int loc)
    {
    	if (length == 0 || loc == length)
    		return -1;
    	else if (list[loc] == item)
    		return loc;
    	else
    	{
    		return seqSearchImpl(item, loc + 1);	//recursive call of seqSearch function
    	}
    
    } //end seqSearch
    If found, it returns the position in the array.

    Code:
    template <class elemType>
    int arrayListType<elemType>::seqSearch(const elemType& item)
    {
    	int loc = 0;
    	seqSearchImpl(item, loc);
    	return loc;
    }
    ...But this function returns loc, which is 0. Since you're not passing loc by reference (which you shouldn't because seqSearchImpl return the pos), it will always return 0, because the local variable isn't changed.

    Instead, consider doing
    Code:
    template <class elemType>
    int arrayListType<elemType>::seqSearch(const elemType& item)
    {
    	return seqSearchImpl(item, 0);
    }
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    Cool, Thanks that was exactly IT! I have been fighting this for hours.
    I can't believe I found the code didn't work when I was 'checking' before submitting.
    Your fix was THE FIX!

    Thanks again, Elysia!
    I appreciate your time with all my 'stupid' errors.
    I am just 5 programs from finishing this class. YAHOO!
    I can see the light! It has been a long dark tunnel.

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed