Using async/await to avoid stack overflow error.

async-await-no-stackoverflow.md

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.

C#

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);
    }
}

TypeScript

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);