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