recursion
Author
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?
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
Hope that helps ya a bit,
ArchG
It's supposed to hurt your head when you think about recursion. That's your brain growing. [smile]
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) ...
I would recommend looking at tree traversal algorithms that use recursion and doing what ArchG said (writing down / drawing the stack on paper) ...
Author
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.
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.
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!
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!
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?)
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?)
To go further on the tree thing ...
assume you have a Binary Tree structure, like this:
then you can do preorder, inorder, and postorder traversal like this:
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 ...
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 ...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
