Problems: When recursion is best

Can anyone provide problems when recursions are the best solutions? Tower of Hanoi is an example.

Any site you know.

Hav u got the solution to Towers of Hanoi? If possible pls post it or send to me directly at [email protected]

many thnx

Yeah.. I have already done that and posted to another thread.

I guess you have already got a copy through your mail.

visit the page http://www.mazeworks.com/hanoi/index.htm
I'm sure you will get the graphical idea to imagine how it works.

If you want to see an instance in which recursion is so much easier and clearer than iteration, look into writing your own binary tree data structure.

I have no idea what it is........forgive me.

Quote:

---

Originally posted by SilentStrike
If you want to see an instance in which recursion is so much easier and clearer than iteration, look into writing your own binary tree data structure.

---

yeah.. I have one.

You have an NxN square, seperated into NxN cells. Find the number of paths from the bottom left cell to the top right cell of the square.

You have two islands. One island has 3 pirates, 3 cannibals, and a boat. The other island is empty. Here are the rules...
1. If there are more cannibals than pirates on an island, then the cannibals eat the pirates, and you lose. (Note that if there are no pirates on an island, then this rule doesn't apply to that island)
2. The only way to move from one island to the other island is the boat.
3. The boat can carry at most 2 people.
4. The boat must carry at least 1 person (to sail it).
Write a program to find a way to get all the cannibals and pirates from one island to the other.

Code:

---

// Since the problem is writing a program, here's a sample solution
PPPCCCB -  // B = Boat
PPCC - BPC // P = Pirate
PPPCCB - C // C = Cannibal
PPP - BCCC
PPPCB - CC
PC - BPPCC
PPCCB - PC
CC - BPPPC
CCCB - PPP
C - BPPPCC
CCB - PPPC
 - BPPPCCC

---

Towers of Hanoi
Finding the nth element, from the union of two sorted sets
Quicksort
Building a 2-3Tree
Traversing a binary tree
Fractals

Recursion is best when:

You have plenty of stack space.
It's faster than not using it.
When working with fractals (Terrain generation comes to mind- midpoint displacement algo, etc.)

I always try to get it iterative first. If that is too ugly or is too slow (or too complicated) then I use recursion.

There are several posts here about how to solve the Hanoi problem. You may have to search through the posts, but they are here.

Thanks QuestionC.
More problems will help to master the logic.