# Recursion Revisited again, and again!

Show 80 post(s) from this thread on one page
Page 1 of 7 1234567 Last
• 12-01-2007
clegs
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.
• 12-01-2007
Elysia
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.
• 12-01-2007
VirtualAce
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```
• 12-01-2007
clegs
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!
• 12-01-2007
matsp
Quote:

Originally Posted by clegs
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
• 12-01-2007
Elysia
Quote:

Originally Posted by matsp
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.
• 12-01-2007
clegs
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.
• 12-01-2007
Elysia
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.
• 12-01-2007
clegs
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!
• 12-01-2007
Elysia
I feel your pain, clegs. But there isn't much we can do but endure :)
• 12-01-2007
clegs
Amen!
• 12-05-2007
clegs
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:
Quote:

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!!!   }   }```
Quote:

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.
• 12-05-2007
Elysia
Quote:

Originally Posted by clegs
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.

Code:

```template <class elemType> int arrayListType<elemType>::seqSearch(const elemType& item) {         return seqSearchImpl(item, 0); }```
• 12-05-2007
clegs
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.