Sign in to follow this  
l jsym l

Recursion in C++

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

... your teacher has never used recursion...

That isn't what jsym wrote:
Quote:

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.

I read this as a teacher who knows how rarely recursion is used in practise. This is in contrast to many "pure academic" teachers who think recursion is so fantastically elegant but never inform their students about the pitfalls and alternatives.

I'd take the former over the latter any day.

Maybe she went a little too far, recursion remains a powerful technique for algorithms that need to backtrack or otherwise remember where they have been.

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
...


Wrong. The teacher has never used recursion in the OP's life. Maybe we are talking about the wrong thing here [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
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.


How large are we talking about? and can you do it without increasing stack size? My simple test crashed when filling a 256x256 area, but I could have made a mistake.

Share this post


Link to post
Share on other sites
Quote:

Wrong. The teacher has never used recursion in the OP's life. Maybe we are talking about the wrong thing here

That is what I meant - the OP's life, not the teachers which others seemed to be saying (hence me quoting the word never).

I'm assuming the teacher is older than the OP, and that saying is roughly equivalent to "I haven't had to solve a problem using recursion in a long time", as I imagine it was probably exaggerated for effect.

Share this post


Link to post
Share on other sites
Has anyone considered the possibility that it might have been a typo?

I'm a beginner C++ programmer (small hobbyist projects for about 5 years, starting formal education now) and I've already used recursion several times to good effect. A few examples:

- 3D terrain generation
- creating randomised 3D models of trees and vegetation for scenery
- Scene graph management

I'd imagine recursion is used heavily in procedural graphics of all sorts.

My personal opinion (though it may be of little value) is that you will definitely find it useful, especially if you're doing any kind of game programming.

Share this post


Link to post
Share on other sites
Quote:
Original post by _swx_
...

Yes, recursion has this limit, I was talking more about simplicity and effectiveness (coding/reading effectiveness too).

Anyway, 256x256 isn't so much, I have 250x250 but 8 directions (minesweeper). If you avoid using variables, it shouldn't be much. I only carry x,y values, if more needs to be used, I put them into a struct so I only have one pointer. And no internal whole-function-scope variables.
I remember an open-source dos program which could floodfill 640x480 without any problems. It used recursion.

But I am curious about the iterative implementation, mine was a very ugly one. (lots of nested loops/if conditions).

Share this post


Link to post
Share on other sites
I use recursion mostly in two cases:
* Depth-first search, or similar backtracking algorithms (including alpha-beta search for game trees).
* Dynamic programming.

You can often get a dynamic-programming solution to a problem by first writing a recursive solution and then memoizing the function.

Share this post


Link to post
Share on other sites
Recursion (excluding tail-recursion which is really just iteration) is pretty much only practical when the recursion depth is O(log n) or better. http://en.wikipedia.org/wiki/Flood_fill#Scanline_fill describes the algorithm I used.

Share this post


Link to post
Share on other sites
Quote:
Original post by _swx_
Recursion (excluding tail-recursion which is really just iteration) is pretty much only practical when the recursion depth is O(log n) or better. http://en.wikipedia.org/wiki/Flood_fill#Scanline_fill describes the algorithm I used.


Nice, thanks!

Share this post


Link to post
Share on other sites
Hey, sorry I was vague but when my instructor told me that she was refering to the job she worked at for over 15 years. She said they always found other ways than to use recursion because she thought it was a lot easier. Also, I have to code in three parameters(the symbol to print out(such as "*"), number of *'s to print on the longest line, and a string containing what to print)

there is a string containing what to print because in the exercise we have to print out all three of these
*
**
***
****
***
**
*

****
***
**
*
**
***
****

*
***
****
***
*
(last one is suppose to be a diamond)

I understand how to do all but the logic for recursion.

Share this post


Link to post
Share on other sites
How much of recursion do you understand? Do you for example know that a recursive function consists of a base case and a recursive rule? It's hard to help when we don't know how much you know.

Share this post


Link to post
Share on other sites
Before attacking that problem, try implementing a recursive function that returns the nth integer power of a float, using NO loops. E.g.


float ipowf(const float f,const int n)
{

//return ??
}
//Hint: what do you return if n is 0? What about if it isn't?


After you've done that, try one that finds the nth fibonnacci number

int fib(const int n)
{

}


After you've done both of those,and they work, THEN think about your problem again.

Share this post


Link to post
Share on other sites
The biggest thing with recursion is NO LOOPS, but at the same time, being able to do what a loop "does." Just remember, there has to be some absolute condition which will always be met which can break you from the recursion (also known as a "base case.") to get a definite answer!

Good luck!

-RageD

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this