Помощь с рекурсией и мемоизацией

Помогите, пожалуйста с задачей. Нужно написать код, который принимает два значения (n и k) и выдает значение функции (описана во вложении). Программа работает медленно для больших чисел, и у меня проблемы с пониманием как использовать мемоизацию и не считать уже вычисленные значения раннее.

int F(int n, int i){
    int f;
    int fsum=0;
 
  if(i < n){
    return i;
  }else{
  for(int j = 1; j <= n; j++){
    f = j * F(n, i-j);
    if(j%2==0){
        f=-f;
    }
    fsum+=f;
  }
}
 return fsum;
 
}


int main(int argc, char *argv[]){
  int n, k;
  scanf("%d %d", &n, &k);
  printf("%d\n",F(n, k));
  return 0;
}

Модератор: Для оформления исходников есть тэг [ SRC ]

Мемоизация - это запоминание однажды посчитанного, т.е. кэширование.

Схематично так работает:

func F(n, k) {
   res = cache.find(n, k); // проверка кэша на наличие ответа для конкретных (n, k)
   if(res != NULL) return res; // если есть ответ - возврат его
   ... расчет res
   cache.add(n, k, res); //сохранение в кэш ответа для конкретных (n, k)
   return res;
}

/* Подсчёт суммы ф-й. На входе n + i, а ф-я должна пробежать от 1 (j) до максимума (n) с учётом (i) в формуле.

n = сколько раз суммировать тело из sum1 * sum2 * sum3
i = фикс.параметр передаётся в ф-ю
j = итерация
*/

#include <iostream>
#include <cmath>

using namespace std;

//##############################################################################
// суммирование через рекурсию
int F(int n,   int i)
{
    if (i < n)    {return i;}   // по условию

    int itogo = 0;
    for (int j = 1;   j <= n;   j++)
    {
/* debug:
        int sum1 = pow(-1,  (j +1));    // (ok) чётная степень = 1;  нечет = -1. Т.е. нечётный j -> sum1 = 1, чётный j -> sum1 = -1.
        int sum2 = sum1 * j;            // (ok) n=3, i=3, j=3  = 3
        int sum3 = F(n, i - j);         // (ok) рекурсия
        int sum_body = sum2  * sum3;

printf("sum1 = %d, sum2 = %d, sum3 = %d, sum_body = %d\tпри: n = %d,  i = %d,  j = %d\n\n",    sum1, sum2, sum3,  sum_body,  n, i, j);
*/
        itogo += pow(-1,  (j +1))   * j   * F(n, i - j);
    }

    return itogo;
}
//##############################################################################
int main(int argc, char *argv[])
{
    system("clear");

    if (argc != 3)    {cout << "формат запуска: " << argv[0] << " int int (2 целых числа для: n И i)\n\n";    return 0;}

    cout << F(atoi(argv[1]), atoi(argv[2])) << "\n";

    return 0;
}

автор
Мемоизация - это запоминание однажды посчитанного, т.е. кэширование.

в данном случае и так считает мгновенно, даже "./a.out 345873853 193845738"
да и такие простейшие расчёты имхо проще, чем запоминать каждую цифру, а потом ещё if делать на каждую

Здесь нужна не мемоизация а просто некий умный способ сворачивания рекурсии с использованием
частично накопленного результата. Как в фибоначчи. Прямая в лоб реализация - генерирует избыточное
дерево расчетов.

mayton
Здесь нужна не мемоизация а просто некий умный способ сворачивания рекурсии с использованием частично накопленного результата. Как в фибоначчи. Прямая в лоб реализация - генерирует избыточное дерево расчетов.

это уже к математикам на форум
а мы только можем озаботиться, чтобы данные в L1/L2 -кэш попали
ну так они вроде там

Математики тем более таким не занимаются. Это чисто it-шный вопрос.

mayton
Математики тем более таким не занимаются. Это чисто it-шный вопрос.

в первую очередь, это вопрос терминологии.
это не вопрос information technology, над такими вопросами в computer science трудятся.
:))

Так или иначе, в русском языке нет адекватного перевода ни тому, ни другому.
По русски это, в любом случае, дело "программиста".
И, мне кажется, что это скорее хорошо, чем плохо.

Это хорошо.

mayton
Математики тем более таким не занимаются. Это чисто it-шный вопрос.

ну технически вы правы
думаю, математики уже над этой задачей поработали
однако нам тут тоже предложить особо нечего, кроме констант на 1000 значений, например