recursion

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

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) ...

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!

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?)

thanks zahl and stoic, both very helpful :)

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 ...

Thanks Xai. Though, I think that's beyond what my book has covered so far. I'll save it and look at it again when it makes more sense. :)

if you just remember this important point you don't even really have to think all that much about it:
the important point to notice is that there should be a Stopping Point or 'End Condition'.
Here is another, perhaps simpler way to understand recursive processes:

1. Are we done yet? If so, return the results. Without such a termination condition a recursion would go on forever.
2. If not, simplify the problem, solve those simpler problem(s), and assemble the results into a solution for the original problem. Then return that solution.

My easiest suggestion for this recursion thing are the numbers that are like (5!). This is 5+4+3+2+1. The function calls itself until it gets down to 0, then returns. I don't have time to do the actual code, but it is an easier example than the towers. :)

Bah, I dislike recursion, although it definitely has it's own time and place. Anyway, I've found it helps to, as was noted earlier, step back from the computer, and write things out on a piece of paper. Does wonders for the comprehension (sp?), that does.

one more thing to say about recursion's time and place:

anything which can be implemented without recursion, and without a stack, should be ...

but anything which would use a stack data structure to hold data, and use it in the limited way that can be turned into recursion, often becomes more readable and debugable to do so.

I've seen people use recursion wrong ... to do things that never requried a stack or any growing collection of data to solve. If you do this, you are making the algorithm inheirently less resource efficient by using a stack / recursion.

For instance trying to turn looping into recursion is crazy:

for(int i=0; i<10; ++i)
{
myFunc(i);
}

recursiveFor(int currentValue, int stopValue, FuncPointer function)
{
if(currentValue < stopValue)
{
function(currentValue);
recursiveFor(currentValue+1,stopValue,function);
}
}

recursiveFor(0,10,myFunc);


I hope you can see how silly this type of recursion would be ... efficiency wise. But I also hope it helps you see how recursion somewhat relates to looping concepts ...

However, in languages that are build for recursion, it makes a lot more sense to use recursion for looping than it normally would:

' Warning, I'm rusty... but something like:(define apply-values (lambda func current limit)  (cond current     (limit ())    (cons (func current) (apply-values func (+ 1 current) limit))  ))(apply-values myfunc 0 10)

alright well ill give you a simple recursion to illustrate the basic concept
for example using !5( some one posted it but no code)

int factorial(int X){	if(X>1)	{	      return(X * factorial(X-1));	}	else	      return(X);}

the recursion happens because the function calls it self unless X is equal to or less than 1. when X is equal to one this function will stop calling itself and instead return X (1 in this case)

it rolls out like this

fact(5  )-> if 5 > 1 return 5 * fact(5-1)fact(5-1)-> if 4 > 1 return 4 * fact(4-1)fact(4-1)-> if 3 > 1 return 3 * fact(3-1)fact(3-1)-> if 2 > 1 return 2 * fact(2-1)fact(2-1)-> if 1 > 1 ELSE return 1

it will hit the case with X == 1 and stop calling itself then the stack unwinds such that 1 is returned giving you this :

fact(2-1)-> if 1 > 1 ELSE return 1fact(3-1)-> if 2 > 1 return 2 * 1fact(4-1)-> if 3 > 1 return 3 * 2fact(5-1)-> if 4 > 1 return 4 * 6fact(5  )-> if 5 > 1 return 5 * 24           RETURN 120

hope this helps some.

I like to think of recursion from a few different aspects.

Firstly, some data structures are recursive, such as trees. So a recursive algorithm fits well with the recursive structure. eg. For each node, do something, then call this on the child nodes.

Also, I think of it in terms of problem solving. How do I get to place D from A? I don't know, but I can get to D from C. So how can I get to place C from A? I don't know, but I can get to C from B? How can I get from A to B - directly. Now I have my route. Recursion is like this. Solving a problem might seem simple but you can't see the answer directly. Instead, you find a new situation that will help you get to the answer, and repeat the process to find the way to that situation. Towers of Hanoi is like this - to get a block to a certain place, you need to be able to move it. To be able to move it, you need to move blocks from above it. To move them... you get the idea. Solving any problem can be viewed in terms of solving one or more smaller problems, until you get to the point where solving the problems is trivial.

Proof by mathematical induction is another concept that applies here. The final calls of your recursion are like the base cases that prove the model, and the recursive calls are like proving one case is true in terms of another case. It doesn't really help you program recursive functions but it's another situation where a recursive definition is considered a good model for a problem.

Quote:

Original post by Xai For instance trying to turn looping into recursion is crazy.

When optimized for tail recursion, your example is perfectly equivalent to a loop.

Also, an important place where recursion should be used is where a problem can be expressed simply in terms of two or more mutually recursive functions.

The problem with most courses/books teaching recursion is they don't give you a useful example - they give you towers of hanoi. The most important thing you need to know is when to apply it (when you realize the main task you need to do gets broken down into smaller tasks that do the same proccessing as the main task). Then you just need a function that first checks for a zero or end condition, then either a)does stuff and returns if zero condition is met or b) does stuff and calls itself again if zero condition is not met. Don't go out of your way to make a solution recursive, if recursion would be useful it will probably be apparent.

A good example, where do you see lots of -R flags for recursion? On pretty much every *nix command that deals with traversing directory structures! Try making your own method that accepts a directory as an argument and prints out directory/filename for each file in the directory and all subdirectories. The method should grab a listing of it's directory, and determine if each item in the list is a file or directory. If it's a file it prints currentdirectory/filename to stdout, if it's a directory it recurses. The zero condition would be when the directory passed to the method contains no subdirectories.

I know this is simple and isn't exactly what you would implement for a real directory listing, but it's something you can probably piece together on your own, and in doing so recursion will probably be much more clear to you.