Как оптимизировать рекурсию?

#include <iostream>
using namespace std;
int vr(int n)
{
  if (n<3) return n;
  else if (n==3) return 4;
  else return vr(n-1)+vr(n-2)+vr(n-3);
}
int main()
{
  int n;
  cin >> n;
  cout << vr(n);
  return 0;
}

Ну, начать с того, что если вы хотите ограничиться int'ами, то в принципе можно оставить рекурсию как есть :) - все равно последнее помещающееся в int значение получается для 36.

А вот если взять unsigned long long, то, конечно, просто так оставить все нельзя. Конечно, можно отказаться от рекурсии, но мы не ищем легких путей? :)

Так что если вы непременно хотите оставить рекурсию - воспользуйтесь такой разновидностью динамического программирования, как мемоизация :)

unsigned long long vr(unsigned int n)
{

    // Размера массива 100 хватит за глаза, потому что 
    // последний помещающийся в unsigned long long результат
    // получается при n == 73
    static unsigned long long v[100] = {0};

    if (n<3) return n;
    else if (n==3) return 4;
    else
    {
        if (v[n]) return v[n];
        return v[n] = vr(n-1)+vr(n-2)+vr(n-3);
    }
}

Это "Числа трибоначчи"

#include <iostream>
int main()
{
  unsigned K;
  std::cin >> K;
  unsigned long long n = 0;
  for (unsigned long long a = 0, b = 0, c = 1; K > 0; --K, a = b, b = c, c = n)
     n = a + b + c;
  std::cout << n << std::endl;
}

Или просто

#include <cmath>
#include <iostream>
int main()
{
  unsigned K;
  std::cin >> K;
  double tribo = 0x1.584c2ef9f4ab1p-2 * std::pow(0x1.d6db7f2d9c5c1p+0, K + 1);
  //                   ^^^ A                            ^^^ B
  // A = 0.336228116994941094225362954014332415157926090020459280443
  // B = 1.839286755214161132551852564653286600424178746097592246778
  std::cout << (unsigned long long) (tribo + 0.5) << std::endl;
}

Точные константы в исходной формуле иррациональны. Точности десятичного разложения, приведенного в комментариях, достаточно для вычисления ответа вплоть до 208 члена последовательности, при условии отсутствия потери точности при выполнении вычислений. При использовании типа double (IEEE754 double precision) расхождение возникнет уже на 56 члене последовательности. При использовании типа long double (IEEE754 extended precision) расхождение возникнет на 67 члене последовательности.

if (n<3) vr=n; else if (n==3) vr=4; else vr=(n-2)*3;

Спасибо https://ru.stackoverflow.com/users/215103/holyblackcat за наводку

   #include <iostream>
    using namespace std;
    int main()
    {
      long n;
      cin >> n;
      n++;
      long arr[n];
      arr[1]=1;
      arr[2]=2;
      arr[3]=4;
      for (int i=4;i<n;i++)
      {
        arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
      }
      cout << arr[n-1];
      return 0;
    }