Jump to content
  • Advertisement
Sign in to follow this  
l jsym l

Recursion in C++

This topic is 2844 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, my teacher for my C++ class was talking about recursion and of how she has never used it in my life but i find it kind of interesting. I understand that I will probably never use it and there are alternatives that are better to use. However, I was looking through my chapter questions (not assigned to me, just doing them on my free will) and saw a question that asked to print out this diagram using recursion:
*
**
***
****
***
**
*
The question says I have to pass a function three parameters and use recursion.
I understand if no one can answer this question I have but I'm just curious. I was just wondering how the logic would be or what it would contain to complete this task.

Thanks. If you need any more information that would be greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
It's hilarious that they tell you how many parameters to pass in but not what they are. (It's not hilarious that your teacher has never used recursion -- it's just sad.) If you want a slight hint, try making a function which prints this instead:

****
***
**
*

Then, switch the print statement and the recursive call and watch as this is printed:

*
**
***
****

Then, finally, change it into the function you want.

Share this post


Link to post
Share on other sites
When I first learnt recursion I hated it & I was told it wasn't used much at all.

But in making my personal projects I have come across alot of occasions where recursion was perfect for. So if I have come across occasions just in my personal projects for recursion, I wouldn't believe that you would never use it in ur proffessional career.

The practical applications of recursion(when I learnt it I wanted to know why & when u would need recursion) include 'searching a folder & identifying all the files in that directory & its sub directories'

In suedo code you would use recurion to search the folder like this:



void getFiles( stack <File> files, vector <File> &foundFiles )
{
// Bare with me I forgot how to open a directory but consider that...
// ..files are all the contents in a directory, they can be files or directories/folders

// while there are still files to search
while ( getNextFile() != 0 )
{

// if file.top() == a directory
// get all files in the sub-directory file.top() & place in a stack( newStack)
// call getFiles( newStack, foundFiles ); // ie recursion

// else foundFiles.add( getNextFile() );

}

return;
}


Share this post


Link to post
Share on other sites
Did your teacher never use recursion really? Well, I'm biased since my main spare time project is a raytracer :-)

Anyway, to go back to your exercise: each recursion level can tell you how many * you need to draw (first call just one, second call two and so on). So this number increases at each call, but kind of 'decreases' when the function ends and the control returns to the caller, right?

So what about drawing the top half of the diagram before the recursive call, and the bottom half just after?

And wich parameter do you need? For example, the max length the rows must reach, and the current length.

Perhaps I've said too much, and I've been vague on pourpose. Good luck for the exercise (and recursion can be extremely useful, as I once discovered in an university project when using recursion solved brillantly a problem we had and that we previously hacked with iteration).

Share this post


Link to post
Share on other sites
Quote:
Original post by l jsym l
I understand that I will probably never use it and there are alternatives that are better to use.

Sounds like someone has been lying to you. Recursion is a very powerful and elegant technique. Some problems are a lot easier to solve with recursion than without it.

Share this post


Link to post
Share on other sites
Quote:
Original post by cignox1
(and recursion can be extremely useful, as I once discovered in an university project when using recursion solved brillantly a problem we had and that we previously hacked with iteration).


Yes.
How would one make a floodfill without recursion for example? I made once. It was the mostest horriblest code I've ever written in this miserable life.

Share this post


Link to post
Share on other sites
Recursion and tree structures go hand in hand. And tree structures (such as file systems, as in gretty's example) are very useful.

[edit] Very deep recursion in c++ can be a problem though since it has limited stack size, especially if you're developing for embedded systems. On a computer you can set the stack size at compile time to something safe for your application.

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
Yes.
How would one make a floodfill without recursion for example? I made once. It was the mostest horriblest code I've ever written in this miserable life.


Try flood filling a large picture with your recursive code... Flood filling can very easily and effectively be inplemented iteratively if you approach it correctly.

Share this post


Link to post
Share on other sites
Quote:
Original post by _swx_
Quote:
Original post by szecs
Yes.
How would one make a floodfill without recursion for example? I made once. It was the mostest horriblest code I've ever written in this miserable life.


Try flood filling a large picture with your recursive code... Flood filling can very easily and effectively be inplemented iteratively if you approach it correctly.


Done both. with MY recursive code and iteratively too. Maybe I approached it wrongly, but I can't imagine anything easier than recursion for this. I would be surprised if the 5 line recursive code can be effectively replaced with an iterative method.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!