Recursion: when do you use it?
 

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:Wich algorithms are they, can someone give me some examples :?:
I mean, when do you really know you HAVE TO USE recursion :?:

Re: Recursion: when do you use it?
 

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.

Re: Recursion: when do you use it?
 

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

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

What do you mean by this :?:

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

Re: Recursion: when do you use it?
 

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

Re: Recursion: when do you use it?
 

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

Re: Recursion: when do you use it?
 

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

Re: Recursion: when do you use it?
 

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