Inspired by elizarov/DeepRecursiveFunction.kt.
Normally, when recursively evaluating the depth of a deep tree, it will result in stack overflow error. But, by using async/await, it keeps its stack on the heap, and evaluates correct result without error.
public static class Program
{
public class Node
{
public Node Left { get; set; }
public Node Right { get; set; }
}
public static uint Depth(this Node node)
{
static async Task<uint> RecurDepth(Node node)
{
if (node == null)
{
return 0;
}
await Task.Yield(); // Avoid direct recursion.
var leftDepth = await RecurDepth(node.Left);
var rightDepth = await RecurDepth(node.Right);
return Math.Max(leftDepth, rightDepth) + 1;
}
return RecurDepth(node).Result;
}
public static void Main(string[] args)
{
var depth = Enumerable.Range(0, 100000)
.Aggregate<int, Node>(null, (root, _) => new Node
{
Left = root,
Right = null,
})
.Depth();
Console.WriteLine(depth);
}
}
type Tree = [Tree, Tree] | null;
function depth(root: Tree): Promise<number> {
async function recurDepth(root: Tree): Promise<number> {
if (!root) {
return 0;
}
await undefined; // Avoid direct recursion.
const leftDepth = await recurDepth(root[0]);
const rightDepth = await recurDepth(root[1]);
return Math.max(leftDepth, rightDepth) + 1;
}
return recurDepth(root);
}
let root: Tree = null;
for (let i = 0; i < 100000; ++i) {
root = [root, null];
}
depth(root)
.then(console.log);