How do methods "call themselves"? Here's an example method called Add():
@functions{ public static int Add(int number){ if(number > 0){ return number + Add(number -1); } return 0; } }
This method takes an int and then repeatedly calls itself reduces the number by 1 until it reaches 0, and returns the sum of all the reductions. So if you passed 4 into the method, it would return 10 (4 + 3 + 2 + 1). You can see this method at work in the Basic example in the article's accompanying code:
@{ Page.Title = "Basic Example"; var input = Request["number"].AsInt(); var result = Add(input); } <div> Result: @for(var i = input; i > 0; i--){ @i @(i == 1 ? " = " : " + ") } @result </div> <form method="post"> @Html.Label("Enter number: ", "number") @Html.TextBox("number", input, new { size = "5" }) <input type="submit" /> </form> @functions{ public static int Add(int number){ if(number > 0){ return number + Add(number -1); } return 0; } }
The recursive method features two mechanisms for preventing infinite loops resulting in a stack overflow: the first is a condition under which the method continues to recurse. In this case, the number must be greater than 0. This is usally termed the "base case". Second is a means to ensure that the base case is reached. In the Add method, that is achieved by reducing the method input value by one on each recursive call.
Hierarchical data is data that is structured in a tree-like manner. There is a single root. The root will have branches, which can have branches, which can have branches.... and so on infinitely.
Individual nodes in this type of structure can be represented in C# in the following manner:
public class Node { public int Id { get; set; } public int? ParentId { get; set; } public string Name { get; set; } }
Each item has an Id and a name. It also optionally has a parent (represented by a nullable int). Roots do not have parents so their ParentId value will be null. All other items in the structure should have a ParentId value that matches the Id of an existing node. This pattern is commonly used to express menu systems, tree views, threaded discussion boards and so on. Here is how you might use the Node class to build a menu:
var menu = new List<Node> { new Node {Id = 1, ParentId = null, Name = "File"}, new Node {Id = 2, ParentId = 1, Name = "Open"}, new Node {Id = 3, ParentId = 1, Name = "Save"}, new Node {Id = 4, ParentId = 1, Name = "Export"}, new Node {Id = 5, ParentId = 4, Name = "To PDF"}, new Node {Id = 6, ParentId = 4, Name = "To Word"}, new Node {Id = 7, ParentId = 6, Name = "Doc"}, new Node {Id = 8, ParentId = 6, Name = "DocX"}, new Node {Id = 9, ParentId = 1, Name = "Exit"} };
"File" is the root node. It has no parent. "Open", "Save", "Export" and "Exit" are all descendants of the root node. "To PDF" and "To Word" are both descendents of "Export", and "Doc" and "Docx" are children of "To Word". What is needed now is a way to generate the HTML to display this menu. A helper is the best way to cater for that:
@helper BuildMenu(List<Node> menu, int? parentid = null, int level = 0) { var items = menu.Where(m => m.ParentId == parentid); if (items.Any()) { if(items.First().ParentId.HasValue){ level++; } foreach (var item in items) { <div> @for (var i = 0; i < level; i++) { @: } @item.Name </div> @BuildMenu(menu, item.Id, level); } } }
The method is called within the page as follows:
@BuildMenu(menu)
All of the Nodes are passed in to the method, which then extracts just those nodes with a ParentId value equal to the one passed in. On the first call, this value is the default value for the paramter - null. So the method extracts the root node if there is one. The the "base case" is established:
if (items.Any()) {
If any nodes meet the criteria in the LINQ Where clause, the first item in the resulting sequence is examined to see if it has a ParentId value. If it does, the value of the level variable is increased by one since this is not the root node. Then each node in the sequence is rendered in a div, and then passed into the BuildMenu method itself - resulting in the hierarchical tree being walked until there are no more nodes. As each level is traversed, the number of non-breaking spaces is added to the output to indent the display:
The Menu example in the accompanying sample site includes a second root node to illustrate how to display multiple multiple menus horizontally.
Working with hierarchical data from a database
You are most likely to store your hierarchical data in a database, so this section looks at how to manage that. The data will represent a simple Tree View. It is stored in a table called Nodes with the following schema:
Id int NOT NULL IDENTITY Primary Key ParentId int Text nvarchar(50) DisplayOrder int DEFAULT 0
The schema bears an obvious resemblence to the Node class definition with the addition of a new property - DisplayOrder. This will be used to determine the order in which items are listed under their parent when CRUD is added later. The helper that is used to render the Tree View to the browser is very similar to the previous one:
@helper BuildTreeView(IEnumerable<dynamic> data, int? parentid = null, int level = 0) { var nodes = data.Where(n => n.ParentId == parentid).OrderBy(n => n.DisplayOrder); if (nodes.Any()) { if(nodes.First().ParentId != null){ level++; } foreach (var node in nodes) { <div style="padding-left:@(level * 20)px;"> @node.Text </div> @BuildTreeView(data, node.Id, level); } } }
This helper expects the result of a Database.Query call to be passed into it. The two other differences from the Menu helper are that the LINQ query has an OrderBy method chained to the Where method, and the indentation for each level is managed by applying a padding to the div rather than preceding each item with non-breaking spaces.
My first introduction to recursion came by way of a classic ASP threaded discussion board. It worked, but it was terribly slow in terms of performance. This was because the recursive method included a call to the database to get records for a specific level each time the method executed. Calls to databases are relatively expensive, so they should be minimised. Ideally, if you want to iterate over data obtained from a database multiple times in your code, you should only ever obtain the data once. That is exactly how this helper has been designed; the code to obtain the data is only ever executed once, and then all the data is passed into the method:
@{ var db = Database.Open("TreeView"); var treeView = db.Query("SELECT * FROM Nodes"); } @BuildTreeView(treeView)
Adding Nodes
Here is a simple form for adding new nodes:
<h1>Add Node</h1> <div> @message </div> <form method="post"> <div> @Html.Label("Text: ", "Text") @Html.TextBox("Text", Request["Text"]) @Html.ValidationMessage("Text") </div> @if(nodes.Any()){ <div> @Html.Label("Parent: ", "ParentId") @Html.DropDownList("ParentId", nodes) </div> } <div> @Html.Label("Display Order: ", "DisplayOrder") @Html.TextBox("DisplayOrder: ", displayOrder, new { size = 2 }) @Html.ValidationMessage("DisplayOrder") </div> <div> <input type="submit" /> </div> </form>
There is a text box for the name of the node and a dropdown list includes all existing nodes so that a parent can be selected. Finally, the display order can be provided in another text box. It is prepopulated with the default value of 0. Usually, items are retrieved from the database in the order that they went in if there is no ORDER BY clause specified, but that cannot be relied upon. In any event, if you delete nodes and subsequently add new ones, you need some way of controlling the order in which they are displayed - hence the DisplayOrder column and the OrderBy method in the LINQ query.
Here is the code block at the top of the Add page:
@{ Validation.Add("Text", Validator.Required(), Validator.StringLength(50)); Validation.Add("DisplayOrder", Validator.Integer()); var db = Database.Open("TreeView"); var sql = string.Empty; var message = string.Empty; var displayOrder = Request["DisplayOrder"].IsInt() ? Request["DisplayOrder"].AsInt() : 0; if(IsPost && Validation.IsValid()){ sql = "INSERT INTO Nodes (ParentId, Text, DisplayOrder) VALUES (@0, @1, @2)"; var text = Request["Text"]; var parentId = Request["ParentId"].IsEmpty() ? DBNull.Value : (object)Request["ParentId"]; db.Execute(sql, parentId, text, displayOrder); message = text + " added"; } sql = "SELECT * FROM Nodes"; var treeView = db.Query(sql); var nodes = treeView.Select(item => new SelectListItem { Value = item.Id.ToString(), Text = item.Text, Selected = item.Id.ToString() == Request["ParentId"] }); }
Validators are used to ensure that a value of the Text property is provided and that it doesn't exceed the size of the database column. Also, the DisplayOrder value must be an integer. If validation passes, the data is inserted into the database. If the ParentId value is not provided, DBNull.Value is inserted into the database to ensue a null value. A message is dsiplayed ot indicate which node was successfully added to the database and then the fresh node data is obtained from the database and used to populate the dropdown list ready for the next node to be added.
Editing and Deleting Nodes
If you are familiar with basic data access using the Database helper, there is nothing particularly interesting about adding nodes. Editing nodes is straightforward too, so long as you are happy for any child nodes to move across with a parent node if you want to change its parent. Deleting nodes is a slightly more complex operation unless you are happy for orphans to be left in the database. Usually this is not a good idea, so if you provide the user with the ability to delete a node, you need to "walk its tree" to identify all child nodes and delete them too.
First, you need to select a node to edit. An easy way to enable users to do this is to display the tree with each node acting as a link. So the previous helper just needs a little modification to the HTML that's generated:
@helper BuildTreeView(IEnumerable<dynamic> data, int? parentid = null, int level = 0) { var nodes = data.Where(n => n.ParentId == parentid); if (nodes.Any()) { if(nodes.First().ParentId != null){ level++; } foreach (var node in nodes.OrderBy(n => n.DisplayOrder)) { <div style="padding-left:@(level * 20)px;"> <a href="~/TreeViewAdmin/EditNode?id=@node.Id">@node.Text</a> </div> @BuildTreeView(data, node.Id, level); } } }
Clicking on a node takes the user to an Edit form for the selected node, which is identified from the query string value:
@if((Request["id"].IsInt() && !IsPost) || (IsPost && !Validation.IsValid())){ <h1>Edit Node</h1> <form method="post"> <div> @Html.Label("Text: ", "Text") @Html.TextBox("Text", nodeText) @Html.ValidationMessage("Text") </div> @if(parentId.HasValue){ <div> @Html.Label("Parent: ", "ParentId") @Html.DropDownList("ParentId", nodes) </div> } <div> @Html.Label("Display Order: ", "DisplayOrder") @Html.TextBox("DisplayOrder", displayOrder, new {size = 2}) @Html.ValidationMessage("DisplayOrder") </div> <div> <input type="submit" name="Action" value="Delete" /> <input type="submit" name="Action" value="Edit" /> </div> </form> }
The form is displayed only there is a valid ID in the query string and the form has not been posted, or if the form has been posted but failed validation. Details of the selected node prepopulate the form for editing. The user has two options - edit or delete. Here's the entire code block at the top of the page:
@{ Validation.Add("Text", Validator.Required(), Validator.StringLength(50)); Validation.Add("DisplayOrder", Validator.Integer()); var db = Database.Open("TreeView"); var nodeSql = "SELECT * FROM Nodes"; IEnumerable<SelectListItem> nodes = null; var nodeText = string.Empty; var displayOrder = 0; int? parentId = null; var data = Enumerable.Empty<dynamic>(); var refreshData = true; if(Request["id"].IsInt() && !IsPost){ data = db.Query(nodeSql); var id = Request["id"].AsInt(); nodeText = data.First(d => d.Id == id).Text; parentId = data.First(d => d.Id == id).ParentId; displayOrder = data.First(d => d.Id == id).DisplayOrder; nodes = data.Select(item => new SelectListItem { Value = item.Id.ToString(), Text = item.Text, Selected = item.Id == parentId }); refreshData = false; } if(IsPost && Validation.IsValid()){ if(Request["Action"] == "Edit"){ var sql = "UPDATE Nodes Set ParentId = @0, Text = @1, DisplayOrder = @2 WHERE Id = @3"; nodeText = Request["Text"]; displayOrder = Request["DisplayOrder"].AsInt(); var pId = Request["ParentId"].IsEmpty() ? DBNull.Value : (object)Request["ParentId"]; db.Execute(sql, pId, nodeText, displayOrder, Request["id"]); } if(Request["Action"] == "Delete"){ data = db.Query(nodeSql); var idList = new List<int>(); var ids = GetIds(data, ref idList, Request["id"].AsInt()); var parms = ids.Select((s, i) => "@" + i.ToString()).ToArray(); var inclause = string.Join(",", parms); var sql = "DELETE FROM Nodes WHERE Id IN ({0})"; var idsArray = ids.Select(i => i.ToString()).ToArray(); db.Execute(string.Format(sql, inclause), idsArray); } } if (refreshData) { data = db.Query(nodeSql); } }
There are three main sections in the code, each responsible for managing a different stage in the process. The first block sets the initial page up with the declaration of a number of variables and validation rules. Right at the bottom of the code block, you can see the most recent node data being retrieved from the database if the refreshData boolean flag is true. When the page is first requested (and after the edit/delete form has been posted) a tree view is displayed:
@if(Request["id"].IsEmpty() || IsPost){ <h1>Select Node</h1> @BuildTreeView(data) }
The next block of code executes when a link in the tree view is clicked - the ID of the node is present in the query string, but no form has been posted. All of hte nodes are retireved form the database and then the one that is subject to being edited is identified and used to populate the dropdown list to allow for selection of a parent (if that is to change) and the rest of the form. There is no need to retrieve this data again for the page, so a boolean flag is set to false to prevent the data selection at the bottom of the block from executing.
The last block of code deals with successful form submission. If the Edit button was clicked, a simnple UPDATE statement is executed to apply any submitted changes ot the databse. The code that manages a DELETE is a bit more complex. In this case, the business rules dictate that no orphaned nodes should be left in the database, so the selected node and all its children must be deleted. In order to achieve that, all the IDs of the affected nodes need to be collected and passed in to an IN clause as part of the SQL DELETE statement. I have already written about how to manage IN clauses with the Database helper, so if you are unclear on that part, please refer to the previous article.
The code to obtain the IDs consist of another recursive method wrapped as a Razor function:
@functions { public static List<int> GetIds(IEnumerable<dynamic> data, ref List<int> ids, int? id = null, int? parentId = null ){ var items = id.HasValue ? data.Where(i => i.Id == id) : data.Where(i => i.ParentId == parentId); if(items.Any()){ foreach(var item in items){ ids.Add(item.Id); GetIds(data, ref ids, null, item.Id); } } return ids; } }
This method has a return type of List<int> which will contain all the IDs. It also features a parameter marked with the ref keyword. The parameter is a List<int>. The ref keyword ensure that a reference to an initialised List<int> is passed in to the method, which means that it will maintain state externally to the method each time the method is called. If the ref keyword was not used, the List<int> would go out of scope each time the method is called and all values except one will be lost. Beyond that, the structure of the method is very similar to the helpers that you have seen already. When the method is first called, it is presented with a List<int> by ref, and the ID of the node to be deleted. On each subsequent method call, all items with a parent id that matches that of the current node are obtained - i.e. its children. Finally, the code converts the List<int> to a comma seaprated string for the database helper.
Performance
The sample site that accompanies this article includes the scenarios covered in this article along with a basic illustration of how a threaded discussion board might work. Recursion is a very useful tool for some scenarios, but it comes at a price. As I mentioned earlier, you need to be careful what you actually do within a recursive function as calls to external processes such as databases can be expensive and might slow your application right down. Also, recursion is a bit like Regex. When people first encounter it, they are impressed with its power and then try to apply it to every problem they come up against. Just as straightforward string manipulation can often be a better solution than Regex, so can a loop be a better bet than recursion. For example, the first recursive method that you were shown can just as easily be replaced with a simple while loop:
@functions { public static int AddWithoutRecursion(int number) { var temp = 0; while (number > 0) { temp += number; number --; } return temp; } }
Recursion uses a stack. Each call to the recursive method is added to the stack, and when recursion is complete, all of the calls are executed. Stacks are limited in size, although you may be able to increase them if you have enough RAM allocated to your shared hosting App pool (or if you have control over the server). If a stack exceeds the size allocated to it, the result is a StackOverflowException:
This was achieved by entering 9000 into the Basic example using the recursive Add method while debugging against IIS Express in Visual Studio. If you try this from WebMatrix, the site will just stop. If the same number is processed using the AddWithoutRecursion method, there is no such problem. If you are not certain many times your method may need to recurse, you should look at alternative approaches using loops and Stacks. However, if you know that your menu or tree view will never approach the kind of size that may cause performance issues, or that the number of posts in a thread will remain within manageable limits, recursion is a neat solution for managing hierarchical data.
The sample site featuring all the examples illustrated here can be found at GitHub.
