I use a lot `T4` templates and want to avoid extra code writing when it could be generated. Currently I have following class:

    class Recursion
    {
        private readonly string _function;
        private readonly Func<int, string> _appFunc;

        public Recursion(string function, Func<int, string> appFunc)
        {
            _function = function;
            _appFunc = appFunc;
        }

        public string Apply(int n)
        {
            return Apply(0, n);
        }

        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 string.Format("{0}({1}, {2})", _function, _appFunc(k), _appFunc(k + 1));
            int half = (n + k) / 2;
            return string.Format("{0}({1}, {2})", _function, Apply(k, half), Apply(half, n));
        }
    }

Example of usage:

    var rec = new Recursion("Math.Max", i => string.Format("source[{0}]", i));
    Console.WriteLine(rec.Apply(8));

output:

> Math.Max(Math.Max(Math.Max(source[0], source[1]), Math.Max(source[2],
> source[3])), Math.Max(Math.Max(source[4], source[5]),
> Math.Max(source[6], source[7])))

It works fine but for large files generation takes a lot of time (even when N is small). I can't use it for larger N (now I'm using N = 4 and generation takes 5+ seconds, i expect that for 8 and more it would take hours). 

Maybe whole algorithm is wrong. I want to get this output, but with smaller cost, if possible.