Выдвину версию.
В первом случае программа вычисляет все значения т.е.
f(46) = f(45) + f(44) (1)
при этом f(45) в (1) это
f(45) = f(44) + f(43) (2)
а f(44) в (1)
это f(44)=f(43) + f(42)

уже тут f(44) и f(43) Вычисляется 2 раза каждая, но каждая из них раскрывается в такое же дерево вычислений!!!
мне трудно даже представить сложность, но она колоссальная подозреваю что порядка 2^n т.е 2 в 45 степени

во втором примере, когда компилер инстанирует шаблон класса он запоминает о его существовании и не вычисляет её более. т.е. f(1),f2 .. и т.д.
будут вычислены всего один раз. Тоесть компилеру понадобиться всего 93 темплятных класса.


Другими словами — вся беда в рекурсии и втом что в твоем примере не запоминается уже вычисленный результат. Надо написать нерекурсивную функцию которая будет помнить чему равно f(N) если оно хоть раз вычислялось.