By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,109 Members | 1,007 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,109 IT Pros & Developers. It's quick & easy.

Recursive Search

P: n/a
Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.

I would GREATLY appreciate it!!!

Aug 10 '07 #1
Share this Question
Share on Google+
10 Replies


P: n/a
As******@msn.com wrote:
Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.
What do you know about "recursive" functions ?
Aug 10 '07 #2

P: n/a
On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.

What do you know about "recursive" functions ?
*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.

Aug 10 '07 #3

P: n/a
As******@msn.com wrote:
On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
>Ashee...@msn.com wrote:
>>Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.
What do you know about "recursive" functions ?

*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.
A linked list is one element and one linked list or the empty linked list.

Is that enough of a hint ?
Aug 10 '07 #4

P: n/a
On Aug 9, 9:21 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.
What do you know about "recursive" functions ?
*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.

A linked list is one element and one linked list or the empty linked list.

Is that enough of a hint ?
****************************
Not really...

Aug 10 '07 #5

P: n/a
As******@msn.com wrote:
On Aug 9, 9:21 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
>Ashee...@msn.com wrote:
>>On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.
What do you know about "recursive" functions ?
*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.
A linked list is one element and one linked list or the empty linked list.

Is that enough of a hint ?

****************************
Not really...
Try writing the data structure for a linked list and the outline of a
function. Once you have that think about how to operate on a linked
list like I described above i.e. an element and another linked list, or
the empty list.
Aug 10 '07 #6

P: n/a
On Aug 9, 9:44 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
On Aug 9, 9:21 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.
What do you know about "recursive" functions ?
*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.
A linked list is one element and one linked list or the empty linked list.
Is that enough of a hint ?
****************************
Not really...

Try writing the data structure for a linked list and the outline of a
function. Once you have that think about how to operate on a linked
list like I described above i.e. an element and another linked list, or
the empty list.- Hide quoted text -

- Show quoted text -
Hmmm...ok. Here is what I have so far.
Here is the .cpp file:

#include <iostream>
using namespace std;
#include "List.h" // header file
template< typename NODETYPE>
List< NODETYPE >::List()
:firstPtr( 0 )
{
} // end default constructor

template< typename NODETYPE>
List< NODETYPE >::~List()
{
if ( !isEmpty() )//list is not empty
{
cout << "Destroying Nodes...\n";
ListNode< NODETYPE *currentPtr = firstPtr;
ListNode< NODETYPE *tempPtr;

while ( currentPtr != 0 ) //deletes nodes
{
tempPtr = currentPtr;
cout << tempPtr->Data << '\n';
currentPtr = currentPtr->nextPTR;
delete tempPtr;
}
}

//insert at front
template< typename NODETYPE>
void List< NODETYPE >::insertAtFront(const NODETYPE &value )
{
ListNode< NODETYPE *newPtr = getNewNode( value ); //new node

if( isEmpty() ) //the list IS empty
firstPtr = lastPtr = newPtr;
else //if not empty
{
newPtr->nextPtr = firstPtr;
firstPtr = newPtr;
}
}

//insert at back
template< typename NODETYPE>
void List< NODETYPE >::insertAtBack(const NODETYPE &value )
{
ListNode< NODETYPE *newPtr = getNewNode( value ); //new node

if( isEmpty() ) //the list IS empty
firstPtr = lastPtr = newPtr;
else //if not empty
{
lastPtr->nextPtr = newPtr;
lastPtr = newPtr;
}
}

//delete from front
template< typename NODETYPE>
bool List< NODETYPE >::removeFromFront(const NODETYPE &value )
{
if( isEmpty() )
return false; //unsuccessful delete
else
{
ListNode< NODETYPE *tempPtr = firstPtr;

if (firstPtr == lastPtr )
firstPtr = lastPtr = 0; //no more nodes
else
firstPtr = firstPtr->nextPTR;
value = tempPtr->data;
delete tempPtr;
return true; //successful delete
}
}

//delete from back
template< typename NODETYPE>
bool List< NODETYPE >::removeFromBack( NODETYPE &value )
{
if( isEmpty() )
return false;
else
{
ListNode< NODETYPE *tempPtr = lastPtr;
if (firstPtr == lastPtr )
firstPtr = lastPtr = 0;
else
{
ListNode< NODETYPE *currentPtr = firstPtr;

//locate second-to-last element
while ( currentPtr->nextPtr != lastPtr )
currentPtr = currentPtr->nextPtr; //move to next node

lastPtr = currentPtr; //remove last node
currentPtr->nextPtr = 0; //becomes the last node
}

value = tempPtr->data; //return value from old last node
delete tempPtr; //reclaim former last node
return true; //delete successful
}
} //ends removeFromBack function

//is list empty?
template< typename NODETYPE >
bool List< NODETYPE >::isEmpty() const
{
return firstPtr == 0;
}//end isEmpty function

//return pointer
template< typename NODETYPE >
ListNode< NODETYPE *List< NODETYPE >::getNewNode(const NODETYPE
&value )
{
return new ListNode< NODETYPE >( value );
}//end getNewNode

//display list
template< typename NODETYPE >
void List< NODETYPE >::print() const
{
if ( isEmpty() )
{
cout << "The list is empty\n\n";
return;
}
ListNode< NODETYPE *currentPtr = firstPtr;

cout << "The list is: ";

while ( currentPtr != 0 ) //get element data
{
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
}

cout << "\n\n";
}

int main()
{
List();
void insertAtFront(5);
void insertAtFront(4);
int list;
}//end main

Aug 10 '07 #7

P: n/a
As******@msn.com wrote:
On Aug 9, 9:44 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
>Ashee...@msn.com wrote:
>>On Aug 9, 9:21 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
>Ashee...@msn.com wrote:
>>Hello Everyone!
>>I have a linked list and am trying to include a recursive search.
>>However, I am having trouble understanding how I would go about that.
>>I don't quite understand a recursive search....would any of you be so
>>kind to explain it to me...maybe include some examples.
>What do you know about "recursive" functions ?
*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.
A linked list is one element and one linked list or the empty linked list.
Is that enough of a hint ?
****************************
Not really...
Try writing the data structure for a linked list and the outline of a
function. Once you have that think about how to operate on a linked
list like I described above i.e. an element and another linked list, or
the empty list.- Hide quoted text -

- Show quoted text -

Hmmm...ok. Here is what I have so far.
Here is the .cpp file:
What do you want your search function signature to look like ?
Aug 10 '07 #8

P: n/a
On Aug 9, 10:08 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
On Aug 9, 9:44 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
On Aug 9, 9:21 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:
>Hello Everyone!
>I have a linked list and am trying to include a recursive search.
>However, I am having trouble understanding how I would go about that.
>I don't quite understand a recursive search....would any of you be so
>kind to explain it to me...maybe include some examples.
What do you know about "recursive" functions ?
*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.
A linked list is one element and one linked list or the empty linked list.
Is that enough of a hint ?
****************************
Not really...
Try writing the data structure for a linked list and the outline of a
function. Once you have that think about how to operate on a linked
list like I described above i.e. an element and another linked list, or
the empty list.- Hide quoted text -
- Show quoted text -
Hmmm...ok. Here is what I have so far.
Here is the .cpp file:

What do you want your search function signature to look like ?- Hide quoted text -

- Show quoted text -
See...that is what I am very confused on. I just don't get it.

Aug 10 '07 #9

P: n/a
As******@msn.com wrote:
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.

I would GREATLY appreciate it!!!
I strongly suggest you use a loop instead of a recursive function. If
you have to make a recursive function because this is homework, then
write the looping version and convert it.

Here's a typical loop.

for ( <init; <cond; <update)
<body>

This can be converted to two functions: the main function and the helper
recursive function.

recFunc() {
loopVar = <init>
recHelperFunc( loopVar );
}

recHelperFunc( loopVar ) {
if ( <cond) {
<body>
<update>
recHelperFunc( loopVar ); // recursive call
}
}
Aug 10 '07 #10

P: n/a
As******@msn.com wrote:
See...that is what I am very confused on. I just don't get it.
Ah.

In general you need to know what you're searching for so something like
this would be the entry point:
iterator SearchEqual(const NODETYPE &value )
{
return SearchNodes( firstPtr, value );
}
iterator SearchEqualNodes(Node * ptr, const NODETYPE &value )
{
if ( ptr )
{
if ( value == ptr->Value )
{
return iterator( ptr );
}

return SearchNodes(ptr->nextPtr(), value );
}

return end();
}
Aug 10 '07 #11

This discussion thread is closed

Replies have been disabled for this discussion.