Jump to content
  • Advertisement
Sign in to follow this  
gnomer

recursion

This topic is 4835 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

Just finished the towers of hanoi exercise in my c++ book and I have to say that recursion just makes my brain hurt :P Wondering if anyone has any tips or tricks that helped them get better at reading/writing recursive functions. I'm still not even sure how I did finish the exercise but it works. The next exercise wants me to try it non-recursive (iterative) and I'm not sure I even wanna try after the trouble I had with the recursive version. Any advice?

Share this post


Link to post
Share on other sites
Advertisement
Recursion also gave (and gives) me headaches alot...what I found to help me out is sit back from the computer a second..and write down the stack (what order the functions are called and such) and it should kinda unravel itself more clearly than it appears in the damn code window

Hope that helps ya a bit,
ArchG

Share this post


Link to post
Share on other sites
It's supposed to hurt your head when you think about recursion. That's your brain growing. [smile]

Share this post


Link to post
Share on other sites
of course, the fact that towers of hanoi is a not so obvious problem to begin with problem increases the pain :)

I would recommend looking at tree traversal algorithms that use recursion and doing what ArchG said (writing down / drawing the stack on paper) ...

Share this post


Link to post
Share on other sites
right, I think the towers was just making it tough. I have tried breaking down some problems on paper and it helps but the towers was hard to understand even broken down. I understand the concept of how to solve the towers but putting it into a recursive algorithm was tough stuff.

Share this post


Link to post
Share on other sites
After a while it becomes so normal you don't even think about it. At least for me. I find that I think recursively alot without actually realizing it when I am designing or implementing. It just sort of becomes a common place thing, it is very useful and natural expression.

Share this post


Link to post
Share on other sites
For what it's worth, In college they gave me an interesting way to think of recursion. You take a look at a problem and see if making a move on the problem leads to a problem which is a subset of the original problem, but the same type of problem.

When you encounter a scenario like this, you keep taking steps until the solution to the step you're on is trivial. Then you choose the trivial solution and return up to the next level. Hopefully, solving the trivial case you just solved will make the case up above also trivial. You solve it, and move up, etc... cascading the solution back upwards.

Ha, guess explaining it in words doesn't help too much. Seriously, though, if you look through Tree searches, sort algorithms, etc, that are all recursive, then you find that there's usually very little code involved. There are potentially a bunch of recursive calls, and a couple of lines which solves the problem in the trivial case. THe nastiness just involves figuring out which order to do it all in.

Anyhow, hope it helps out a bit!

Share this post


Link to post
Share on other sites
Towers of Hanoi:

To move 1 disk from a to b:
Just move it.

To move n disks from a to b, for n > 1:
Move the top n-1 disks from a to c. We'll assume we know how to do this for now.
Move the remaining disk to b. This is easy; just move it. There's nothing at b.
Move the n-1 disks from c to b. This is the same as moving them from a to c.

Now we justify that this works (i.e. justify the assumption), by "mathematical induction":

a) We know how to move 1 disk.
b) If we can move k disks, then we can move k+1 disks, by letting n=k+1 and using the algorithm there.

Since we can move 1 disk, (b) says we can move 2 disks. Since we can move 2, we can move 3, and so on for any number.

To do this sort of thing in general, what you need to do basically is ask (a) "what's the easiest possible problem of this type, and how do I solve it?" and (b) "given any problem other than the easiest, can I solve it by cutting it up into easier problems, solved in the same basic way?"

Try it on your own with sorting. The easiest set of things to sort has one thing in it; how do you sort that? Now, if you cut up a set of things into two smaller sets, how can that help you sort the whole thing? (Hint: Take a brand-new deck of cards, so that the cards are already sorted by suit and then by rank. Deal out the cards alternately to two piles neatly - so each pile is now a sorted pile of 26 cards. How would you put this back together? Now, shuffle each of those piles of 26 cards. How do you get a sorted deck back?)

Share this post


Link to post
Share on other sites
To go further on the tree thing ...

assume you have a Binary Tree structure, like this:


template <typename T>
struct BinaryTreeNode
{
T value;
BinaryTreeNode *leftChild;
BinaryTreeNode *rightChild;
};




then you can do preorder, inorder, and postorder traversal like this:


template <typename T>
struct NodeVisitor
{
virtual void VisitNode(BinaryTreeNode<T> *node) = 0;
};

template <typename T>
void InorderTraversal(BinaryTreeNode<T> *node, NodeVisitor<T> *visitor)
{
if(node != 0)
{
InorderTraversal(node->leftChild);
visitor->VisitNode(node);
InorderTraversal(node->rightChild);
}
}

template <typename T>
void PreOrderTraversal(BinaryTreeNode<T> *node, NodeVisitor<T> *visitor)
{
if(node != 0)
{
visitor->VisitNode(node);
PreOrderTraversal(node->leftChild);
PreOrderTraversal(node->rightChild);
}
}

template <typename T>
void PostOrderTraversal(BinaryTreeNode<T> *node, NodeVisitor<T> *visitor)
{
if(node != 0)
{
PostOrderTraversal(node->leftChild);
PostOrderTraversal(node->rightChild);
visitor->VisitNode(node);
}
}




of course, I didn't check for vistor being null, or actualy implement a usefull visitor function (like PrintNode or something) - but I hope by following through that code you can see how expresive recursion can be - for the right situations ...

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!