Recursion: when do you use it?

[JoBe]

Hi ladies and gents,

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

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 :?:

[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. But often recursive functions are easily understood(not for all though :D) 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.

[JoBe]

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 :D) 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 :?:

[Narue]

>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. ;)

[JoBe]

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 :?:

[Narue]

>could you explain what a binary search tree actually is
I can, and I have.

[JoBe]

> I can, and I have.
Thanks Narue, that's a detailed explanation :!: