1) Коли я намагався скомпілювати, то була помилка: функція int foo(void) не містить return.
В себе я поставив void foo(void).

2) Цей код:

for (int i = 0; i < 70000; ++i)
    a += g<1>(i);

Буде формувати величезний стек викликів функцій (близько 140000) і це не нормально. Тому хто тестує, доведеться або збільшити максимальний розмір стеку (а це не бажано), або зменшити діапазон змінної i.

3) В мене теж програма виконується швидше, коли є явний виклик функції f<1>(0) (в мене VS2013).
Думаю справа тут в тому, що коли компілятор бачить f<1>(0), то відповідна реалізація template'а вже готова до використання. А коли його нема, то спочатку формується опис, а потім кожен виклик перенаправляється на реалізацію. Це лише моя думка, і вона може бути неправильна.

Попробуйте в іншому порядку:

template<int Foo>
int f(int num)
{
    if(num == 0) return Foo;
    return num + f<Foo>(num - 1);
}
template<int Foo>
int g(int num)
{
    return f<Foo>(num);
}

В мене так пішло швидше і без f<1>(0).

Щодо функції foo, то тут я протупив, хоча в мене і з int foo(void) компілюється. В принципі, можна і без неї обійтись, тут важливо саме, що десь у коді явно викликається екземпляр f<1>.
Щодо стеку викликів, то про це я не подумав, але тут пишуть, що за замовчуванням його розмір 1МБ. Тут, здається, цього має вистачити.
Зміна порядку визначення функцій f і g в мене на результат не впливає, але я спробував узагалі прибрати шаблони і функцію g:

#include <fstream>
#include <chrono>

using namespace std;

int f(int num)
{
    if (num == 0)
        return 1;
    return num + f(num - 1);
}

int main(void)
{
    int a(0);
    ofstream out("log.txt");
    for (int i = 0; i < 5; ++i)
    {
        auto start = chrono::high_resolution_clock::now();
        for (int j = 0; j < 70000; ++j)
            a += f(j);
        auto end = chrono::high_resolution_clock::now();
        out << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms elapsed " << a << '\n';
    }
    out.close();
    return 0;
}

В цьому випадку швидкодія така ж погана, як і при шаблонах без явного виклику f<1>.
Налаштування оптимізації: