Sequential numbering from recursive function? e.g. 2, 2.1, 2.1.1, 2.2, 2.2.1

Question

I have a recursive function reading a "table of contents" of documents from a database. I would like to print numbering with the document that reflects where the item is in the tree, e.g.

1. First item,
    1.1 Child of first item,
        1.1.1 Child of child of first item,
    1.2 Child of first item,
2. Second item,
    2.1 Child of second item,

etc.

Rather stumped about this at the moment - help please?

Answer 1

It would be useful to see your code. Assuming that the data is stored in some hierarchical representation, the structure of the recursion might look like this:

void PrintTOC(string prefix, List<Sections> sections) {
  // Iterate over all sections at the current level (e.g. "2")
  for(int i = 0; i<sections.Length; i++) {
    // Get prefix for the current section (e.g. "2.1")
    string num = String.Format("{0}.{1}", prefix, i+1);
    // Write the current section title
    Console.WriteLine("{0} {1}", num, sections[i].Titles);

    // Recursively process all children, passing "2.1" as the prefix
    if (sections[i].Children != null)
      PrintTOC(num, sections[i].Children);
  }
}

This keeps a prefix parameter that contains the index of the parent section. All numbers in the current section are appended after this prefix.

Answer 2

Simply include a "path" argument in the function and add to it as you go. Pseudo-code:

function print_rec(String path, Node node) {
  print(path + node.title)
  for (int i=1; i<=node.children.length; i++) {
    print_rec(path+"."+i, node.children[i])
  }
}

Answer 3

What's your database platform? If you're using SQL Server 2005 or higher, you can get this kind of path from a "tree" table (one with a self-referencing key) using a single CTE query. (There are also XML-based techniques for running recursive queries in SQL Server.)

Otherwise, you're going to have to perform the recursion in the client code, as others have suggested. In that case, you might want to consider selecting all of the relevant data before starting the recursion and walking the structure using the object. This way you can avoid a potentially huge number of queries against the database.