Recursive function application
Consider using the string concatenation operator + instead. The reason why this works and is not bad is because behind the scenes the method String.Concat is being called.

While String.Format will have to do a lot of different things, such as parsing, getting the string after and before placeholders to be able to join them and so on.

This is important both on the callback and implementation.

private string Apply(int k, int n)
{
    var diff = n - k;
    if (diff == 0)
        return "0";
    if (diff == 1)
        return _appFunc(k);
    if (diff == 2)
        return _function + "(" + _appFunc(k) + ", " + _appFunc(k + 1) + ")";
    int half = (n + k) / 2;
    return _function + "(" + ApplyB(k, half) + ", " + ApplyB(half, n) + ")";
}

var rec = new Recursion("Math.Max", i =&gt; "source[" + i + "]");


By applying this changes I could measure a 0.5s difference on my machine over 60000 iterations calling apply with 8 which previously took 3s so it was a 17% improvement.

Going with StringBuilder

I was a bit reluctant going with a StringBuilder because it seemed an hard job but when we think two more times about it solutions come. My idea was to put a StringBuilder on a field, so I don't have to pass it has a parameter to the function, and make the method return void.

The StringBuilder is the ideal class to build large strings, it is efficient because it manages an array of characters. It's like having mutable strings. 

    class Recursion
    {
        private readonly string _function;
        private readonly Func&lt;int, string&gt; _appFunc;
        private readonly StringBuilder _builder;
        public Recursion(string function, Func&lt;int, string&gt; appFunc)
        {
            _function = function;
            _appFunc = appFunc;
            _builder = new StringBuilder();
        }
        public string Apply(int n)
        {
            Apply(0, n);
            var result = _builder.ToString();
            _builder.Clear();
            return result;
        }

        private void Apply(int k, int n)
        {
            var diff = n - k;
            if (diff == 0)
            {
                _builder.Append("0");
                return;
            }
            if (diff == 1)
            {
                _builder.Append(_appFunc(k));
                return;
            }
            if (diff == 2)
            {
                _builder.Append(_function)
                .Append('(')
                .Append(_appFunc(k))
                .Append(", ")
                .Append(_appFunc(k + 1))
                .Append(')');
                return;
            }
            int half = (n + k) / 2;
            _builder.Append(_function).Append('(');
            Apply(k, half);
            _builder.Append(", ");
            Apply(half, n);
            _builder.Append(')');
        }
    }


This decreased execution 0.9s upon my previous attempt, on the same circumstances, giving it a total of 46% improvement.