Recursion! do you use it? how can I introduce it gradualy into my code?

[devonrevenge]

I need more recursion in my life, I think that means scratching the way I think entirely and starting again though;

As I always wanted to be a good programmer I still never got round to being more of a recursive person even though I know that this is the only real way to command respect among coders, its just that you have to really brain really hard.

I am starting the problem solving module at uni and while I kick ass at solving problems with less lines of code than everyone else, no one is being anywhere near recursive enough, how does one become more recursive in their lives?

I think recursion is the only way to begin your path to "shit hot at coding'ness" and thats what I want to be, I want to submit something on stack overflow and people to submit in the comments that they got coder crushes on me.

Oh yeah sub question, do you have a coder crush?



here's an example at my first attempt at recursion, I posted it for you guys to see -> http://www.cplusplus.com/forum/lounge/155522/ xD

[S G H]

I fell for it. Damn.

[devonrevenge]

I fell for it. Damn

Makes me think how crap the henchmen in a Steven Segal movie must feel when they lay dying with microwave glass embedded in their neck, then there's that cocky remark Steven would make, totally unnecessary really, mate people really are psycho's for enjoying that telly shit.

[chrisname]

Wait until you learn about Peano numbers.

[htirwin]

What made me good at recursion was reading and doing Lisp programming exercises from The Structure and Interpretation of Computer Programs.

But really many problems are actually really really easy to solve with recursion, and for some of them, only the really good programmers can solve them without recursion.

[Cheraphy]

htirwin wrote:

(sic) for some of them, only the really good programmers can solve them without recursion.

Hadn't considered that subset of problems. Any examples off the top of your head?

[MiiNiPaa]

Any examples off the top of your head?

Divide and conquer algorithms. Like quicksort. Generally you will have to emulate call stack to get rid of recursion.

[pnoid]

If you're just looking for for practice, just about any loop can be rewritten as a recursive function.

[tition]

Conversely, any recursion can be rewritten using loops.

When you come to think about it, when executing your "recursive" code, your computer automatically converts it to "iterative" set of machine instructions .

Recently I had to convert a bitch of a recursive algorithm into iterative execution - it was some nasty thing like:

function1 calls function2 calls function3 calls function4 calls function1.

[Cheraphy]

tition wrote:

function1 calls function2 calls function3 calls function4 calls function1.

I'd call that Rube Goldberg recursion.

[chrisname]

@tition
Was it a recursive descent parser?

[maeriden]

A friend of mine was taught recursion something like this:
When you write a function, you first write the successful case. Then you write the logic to change the arguments and call again.

[tition]

@chrisname:

No, it wasn't, what is a recursive descent parser?

In my calculator, I parse math expressions using a mod of heilos' parser:
http://www.cplusplus.com/forum/lounge/11845/
(the mod is very heavy, I parse expressions as difficult as LaTeX matrices).

For the recursion: it was a complicated mathematical algorithm, the topic of my current research. The area is that of Lie algebras. [If you've heard of the "Exceptionally Simple Theory of Everything" - I am working on the mathematical engine related to those physics theories].

The algorithm was so complex because I was learning, rediscovering, and possibly discovering bits and pieces of math as I went.

[Cheraphy]

what is a recursive descent parser?

It's a type of top-down parser where procedures are mutually recursive.

[beko]

I don't want to be mean, but where is your base case? (Awesome post though xD)

On topic: Do some LISP-like language programming? Scheme for instance: http://htdp.org/2003-09-26/Book/curriculum-Z-H-1.html (This is more of a beginners book)

[D80DSL3A]

Here's a simple example of a problem well suited to recursion.
Plus, I just solved it.

I'm making a minesweeper game to substitute for the version lost when I got a new computer. Windows 8.1 is missing all the games that windows has always come with.

The problem concerns the auto clearing of spaces which occurs when a space with 0 mines around it is cleared. The 8 surrounding spaces are automatically cleared, then if any of these 8 also have 0 mines around it those are cleared around, and so on...

The total area cleared with one click is sometimes quite large. The problem seemed a natural for a recursive approach.
This function is working beautifully:

void mineField::clearSpace( int r, int c )
{
    // base case: space already uncovered or marked with a flag or a ?
    if( ppField[r][c].revealed || ppField[r][c].mark == 'f' || ppField[r][c].mark == '?' ) return;

    ppField[r][c].revealed = true;// clear the space

    // was a space with zero mines around it hit?
    if( ppField[r][c].cnt == '0' )// clear the 8 spaces around this space
    {
        if( r>0 )// 3 across the top
        {
            if( c>0  ) clearSpace( r-1, c-1 );// left
            if( c<cols-1 ) clearSpace( r-1, c+1 );// right
            clearSpace( r-1, c );// center
        }

        if( r<rows-1 )// 3 across the bottom
        {
            if( c>0  ) clearSpace( r+1, c-1 );// left
            if( c<cols-1 ) clearSpace( r+1, c+1 );// right
            clearSpace( r+1, c );// center
        }

        // same row
        if( c>0 ) clearSpace( r, c-1 );// left
        if( c<cols-1 ) clearSpace( r, c+1 );// right
    }

    return;
}

Also, I have a variation on the game in mind that I haven't seen anywhere else yet, so I have to make it myself.

[tition]

That's a good example. I was thinking of what it would take to rewrite this recursion in iterative form, and it doesn't seem obvious to me ...

[LB]

Be aware: although some problems are easier to comprehend using recursion, the overhead of recursing can result in a slower execution time than non-recursive solutions.

[tition]

I disagree with the overhead part. When using recursion, you are putting things on the stack. I am not 100% where the stack is located, but I know it's the fastest memory you've ever used. Making a recursive call is much faster than manually constructing a stack and pushing state in and out of it (which is how you unfold recursion).

I think recursion is a very fast way to do things, very efficient and maintainable.
So far, I've been able to produce only one - but a very serious - reason to prefer non-recursive over recursive implementations of algorithms.

The reason: storing/loading state. If for some reason you want to be able to store an intermediate computation and then load it later, using recursion to do so will be unnecessarily complicated.

By the way, being able to store/load intermediate computations has caused me to convert recursive algorithms to iterative ones on at least 4-5 occasions, so I feel quite confident in my recursion-iteration conversion skills :)

[Disch]

That's a good example. I was thinking of what it would take to rewrite this recursion in iterative form, and it doesn't seem obvious to me ...

For funsies I came up with this (not tested).

It's certainly more complicated than a recursive solution and requires an additional 'fillOrigin' entry in the minefield:

inline bool mineField::canBeRevealed( int r, int c )
{
    if( r < 0 )                     return false;
    if( c < 0 )                     return false;
    if( r >= rows )                 return false;
    if( c >= cols )                 return false;
    if( ppField[r][c].revealed )    return false;
    if( ppField[r][c].mark == 'f' ) return false;
    if( ppField[r][c].mark == '?' ) return false;
    
    return true;
}

void mineField::clearSpace( int r, int c )
{
    if(!canBeRevealed(r,c))
        return;
        
    ppField[r][c].revealed = true;
    if( ppField[r][c].cnt != '0' )
        return;


    ppField[r][c].fillOrigin = -1;      // this is our true origin, so it has no fill origin
        
    /* 8 directions from a given tile arranged like so:
        0 1 2
        3 x 4
        5 6 7
    */
    
    static const int xadj[8] = {-1, 0, 1,-1, 1,-1, 0, 1};
    static const int yadj[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
    
    while(true)
    {
        // r and c are our origin (the current center tile)
        // y and x is the current neighbor we're examining for this tile.
        // dir is the direction y,x are from r,c
        int y, x, dir;
        
        // look to check each direction.  Note we will break out of this loop
        //   if we find a direction that has a 'zero neighbor'
        for(dir = 0; dir < 8; ++dir)
        {
            y = r + yadj[dir];
            x = c + xadj[dir];
            
            if(canBeRevealed(y,x))
            {
                ppField[y][x].revealed = true;
                if(ppField[y][x].cnt == '0')
                    break;
            }
        }
        
        // if we found any zero neighbors, make them our new origin, but
        //   record where we came from so we can go back
        if(dir < 8)  // any zero neighbors?
        {
            ppField[y][x].fillOrigin = dir;
            r = y;
            c = x;
        }
        else         // no zero neighbors
        {
            // can we move back?
            int o = ppField[r][c].fillOrigin;
            if(o >= 0)      // we have an origin, move back to it
            {
                r -= yadj[o];
                c -= xadj[o];
            }
            else            // no origin, and no zero neighbors found, we're done
                return;
        }
    }
}