What is a good example of recursion other than generating a Fibonacci sequence?

Question

Possible Duplicates:
Real-world examples of recursion
Examples of Recursive functions

I see that most programming language tutorial teach recursion by using a simple example which is how to generate fibonacci sequence, my question is, is there another good example other than generating fibonacci sequence to explain how recursion works?

Answer 1

The classic is the binary tree search:

def findval (node,val):     if node == null:         return null     if node.val = val:         return node     if node.val > val:         return findval (node.left,val)     return findval (node.right,val)  findval (root,thing_to_find) 

That may be a little more complex than a simple formula but it's the "bread and butter" use of recursion, and it illustrates the best places to use it, that where the recursion levels are minimised.

By that I mean: you could add two non-negative numbers with:

def add (a,b):     if b == 0:         return a     return add (a+1,b-1) 

but you'd find yourself running out of stack space pretty quickly for large numbers (unless the compiler optimised tail-end recursions of course, but you should probably ignore that for the level of teaching you're concerned with).

Answer 2

The other answers mention various algorithms, which is completely fine, but if you want a bit more "concrete" example, you could list all files in some directory and its subdirectories. The hierarchical file system is a well-known example of a recursive (tree) structure, and you could show depth-first and breadth-first search using this concrete example.