Binary search tree: Question about recursion vs. loops

[Pat0010]

For one of my classes, I have to create a binary search tree and search through it to find a certain number, however, I'm having a little bit of an issue understand the outcome. I think my program works fine, but when I search through the tree using loops and recursion the time it takes to find the number is less than 1 second for both recursion and looping. I've always been told that recursion is faster, so shouldn't there be a difference? Can any explain why this is the case or tell me what I'm doing wrong when it comes to the why I implement the functions?

Looping through the tree:

TNode *nrlookup(TNode *treep, int numbers)
{
	while(treep !=NULL)
	{
		if (treep->data == numbers)	{
			return treep;
		}
		else if (numbers < treep->data)	{
			//cout<<treep->data<<endl;
			treep=treep->left;
		}
		else{
			//cout<<treep->data<<endl;
			treep=treep->right;
		}
	}
	return NULL;
}

Using recursion to go through the tree

TNode *lookup(TNode *treep, int numbers)
{
	if(treep == NULL)
		return NULL;
	if(treep->data == numbers) {
		return  treep;
	}
	else if(numbers < treep->data)
	{
		//cout<<treep->data<<endl;
		return lookup(treep->left, numbers);
	}
	else
	{
		//cout<<treep->data<<endl;
		return lookup(treep->right, numbers);
	}

}

[cire]

I've always been told that recursion is faster, so shouldn't there be a difference?

I would make it a point to verify anything said by whoever's been telling you that.

I would expect no noticeable difference between your functions (although the recursive version may be a smidge slower if your compiler doesn't do tail-call optimization.)

Noticeably absent are your timing code, data set, and compiler settings.


http://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping

[ne555]

> the time it takes to find the number is less than 1 second
computers are fast
your tests are badly designed

> I've always been told that recursion is faster
an algorithm is not going to be faster just because it uses recursion