DaniWeb Forum Index > Software Development > C++

C++ RSS

Recursion: when do you use it?

•

Join Date: Sep 2004

Posts: 421

Reputation: JoBe is on a distinguished road

Solved Threads: 4

JoBe

Offline

Posting Pro in Training

Recursion: when do you use it?

Mar 27th, 2005

Hi ladies and gents,

I made this exercise in wich recursion has to be used and it worked as it should:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void ggd(short x, short y)
{
	short a = 0;
 
	if (y == 0)
	{
		cout<<"The largest common divider is: "<< x <<endl;
	}
 
	else
	{
		a = (x% y);
		x = y;
		y = a;
		x% a != 0 ? ggd(x, y) :cout<<"The largest common divider is: "<< a <<endl;
	}
}
 
int main()
{
	ggd(1147, 851);
 
	cin.get();
 
	return 0;
}
void ggd(short x, short y)
{
	short a = 0;

	if (y == 0)
	{
		cout<<"The largest common divider is: "<< x <<endl;
	}

	else
	{
		a = (x% y);
		x = y;
		y = a;
		x% a != 0 ? ggd(x, y) :cout<<"The largest common divider is: "<< a <<endl;
	}
}

int main()
{
	ggd(1147, 851);

	cin.get();

	return 0;
}

Now, I read the tutorial Dany made about this and she mentions:

•

Although recursion should generally be avoided, there are still algorithms which can only be solved with its use.

Wich algorithms are they, can someone give me some examples

I mean, when do you really know you HAVE TO USE recursion

•

Join Date: Apr 2004

Posts: 353

Reputation: Asif_NSU is on a distinguished road

Solved Threads: 2

Asif_NSU

Offline

Posting Whiz

Re: Recursion: when do you use it?

Mar 27th, 2005

My experience in the world of programming is very short. However, I think every recursive function can be transformed into an iterative version. But often recursive functions are easily understood(not for all though

) and makes the code shorter. So unless you worry too much (and I mean too much) about the effieciency of your program you can adhere to the recursive solution. One thing to remember is that whether the choice is better or not depends on the problem at hand.

•

Join Date: Sep 2004

Posts: 421

Reputation: JoBe is on a distinguished road

Solved Threads: 4

JoBe

Offline

Posting Pro in Training

Re: Recursion: when do you use it?

Mar 27th, 2005

•

Originally Posted by Asif_NSU

My experience in the world of programming is very short. However, I think every recursive function can be transformed into an iterative version.

I know, that's what Dani wrote in her tutorial aswell

•

But often recursive functions are easily understood(not for all though ) and makes the code shorter.

I understand, I wrote with this exercise also a function wich didn't use recursion and I needed to write more code then with the use of recursion :!:

•

So unless you worry too much (and I mean too much) about the effieciency of your program you can adhere to the recursive solution.

What do you mean by this

•

One thing to remember is that whether the choice is better or not depends on the problem at hand.

Well that's the question I asked, when do you know it's better to use RECURSION

•

Join Date: Sep 2004

Posts: 7,540

Reputation: Narue has a reputation beyond repute

Solved Threads: 704

Narue

Offline

Code Goddess

Re: Recursion: when do you use it?

Mar 27th, 2005

>when do you know it's better to use RECURSION
Most of the time, binary search trees are better written with recursive algorithms. Sure, it may be a fun exercise to do them iteratively, but anything but a simple binary search tree will be dreadfully complex without recursion. I haven't met many people who are up to the challenge of writing, say, a fully featured AVL tree without recursion.

So when is it better to use recursion? It's better when you can guarantee two things:

1) Each recursive step breaks down the problem into a smaller problem of the same type.
2) Each recursive step reduces the problem significantly.

The first is a general rule of recursion. If each step doesn't break the problem down into a smaller problem of the same type, it's harder to write a recursive function and guarantee that it will terminate. The second is my personal guideline. I generally won't write a recursive function unless it divides the problem in half with each step. This way I can verify with relative ease that the algorithm will be efficient.

>when do you really know you HAVE TO USE recursion
There are no situations where you have no choice but to use recursion. Any recursive algorithm can be converted to an interative algorithm through the use of a stack. The only question is how much work it takes to do this.

I'm here to prove you wrong.

•

Join Date: Sep 2004

Posts: 421

Reputation: JoBe is on a distinguished road

Solved Threads: 4

JoBe

Offline

Posting Pro in Training

Re: Recursion: when do you use it?

Mar 27th, 2005

Thanks for the clear and informative explanation Narue :!:

>Most of the time, binary search trees are better written with recursive algorithms.
One question about this tough, could you explain what a binary search tree actually is