Can someone show me how to implement a recursive lambda expression to traverse a tree structure in C#.
A recursive lambda expression is the process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily.
Recursive Lambdas in C++ auto fib = [](int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }; auto i = fib(7);
Recursive definitions can also be used to define minimalization. It turns out that every recursive definition in the lambda calculus can be ``solved'' by finding its fixed point.
C++ Lambda expression allows us to define anonymous function objects (functors) which can either be used inline or passed as an argument. Lambda expression was introduced in C++11 for creating anonymous functors in a more convenient and concise way.
Ok, I found some free time finally.
Here we go:
class TreeNode
{
public string Value { get; set;}
public List<TreeNode> Nodes { get; set;}
public TreeNode()
{
Nodes = new List<TreeNode>();
}
}
Action<TreeNode> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
var root = new TreeNode { Value = "Root" };
root.Nodes.Add(new TreeNode { Value = "ChildA"} );
root.Nodes[0].Nodes.Add(new TreeNode { Value = "ChildA1" });
root.Nodes[0].Nodes.Add(new TreeNode { Value = "ChildA2" });
root.Nodes.Add(new TreeNode { Value = "ChildB"} );
root.Nodes[1].Nodes.Add(new TreeNode { Value = "ChildB1" });
root.Nodes[1].Nodes.Add(new TreeNode { Value = "ChildB2" });
traverse(root);
A proper solution, and indeed the idiomatic solution in many functional programming languages, would be the use of a fixed-point combinator. In a nutshell: a fixed-point combinator answers the question “how do I define an anonymous function to be recursive?”. But the solution is so nontrivial that whole articles are written to explain them.
A simple, pragmatic alternative is to “go back in time” to the antics of C: declaration before definition. Try the following (the “factorial” function):
Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);
Works like a charm.
Or, for a pre-order tree traversal on an object of class TreeNode
which implements IEnumerable<TreeNode>
appropriately to go over its children:
Action<TreeNode, Action<TreeNode>> preorderTraverse = null;
preorderTraverse = (node, action) => {
action(node);
foreach (var child in node) preorderTraverse(child, action);
};
A simple alternative is to “go back in time” to the antics of C and C++: declaration before definition. Try the following:
Func<int, int> fact = null; fact = x => (x == 0) ? 1 : x * fact(x - 1);
Works like a charm.
Yes, that does work, with one little caveat. C# has mutable references. So make sure you don't accidentally do something like this:
Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);
// Make a new reference to the factorial function
Func<int, int> myFact = fact;
// Use the new reference to calculate the factorial of 4
myFact(4); // returns 24
// Modify the old reference
fact = x => x;
// Again, use the new reference to calculate
myFact(4); // returns 12
Of course, this example is a bit contrived, but this could happen when using mutable references. If you use the combinators from aku's links, this won't be possible.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With