Almost every article I can find about recursion includes the examples of factorial or Fibonacci Numbers, which are:


Math
Useless in real life


Are there some interesting non-math code examples to teach recursion? 

I'm thinking divide-and-conquer algorithms but they usually involve complex data structures.

Directory / File structures are the best example of a use for recursion, because everyone understands them before you start, but anything involving tree-like structures will do.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}

