0

So I have recursive function that needs to be memoized since it takes so long to run. I understand that you store it in a cache, but need help doing that. Also one thing I noticed was that when I printed the value after the function call, I would get the correct value, but when i removed it, the answer would be wrong. Any help is appreciated. The function is supposed to calculate the probability of getting a number after a rolling a s sided die that isn't within 1 of the previous roll after rolling t times

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <vector>
using namespace std;

double dond(int s, int t, int l);

int main(int argc, char *argv[]) {
    int s, t, l;

    s = atoi(argv[1]);
    t = atoi(argv[2]);
    l = atoi(argv[3]);
    //printf("%d %d %d\n", s, t, l);

    cout << dond(s, t, l) << endl;
}

double dond(int s, int t, int l) {
    int i, j;
    double a, d = 0, yuh = 1.0/s;
    vector <double> cache;

    if(t == 1 && l == -1) return 1;
    if(t == 1) {
        if(l == 0 || l == s-1) return (s-2)/(double)s;
        else return (s-3)/(double)s;
    }
   for(i = 0; i < s; i++) {
       if(l == -1 || (i != l && i != l-1 && i != l+1)) {
           cache.push_back(dond(s, t-1, i)); //store into cache
          // printf("A: %f\n", a);
          //printf("",a );
       }
    }
    for(i = 0; i < cache.size(); i++) a += cache[i];
    return yuh * a;
}
jordan neely
  • 39
  • 1
  • 6
  • That's not how memoization works. – Sam Varshavchik Dec 06 '18 at 00:45
  • @SamVarshavchik what am i doing wrong? – jordan neely Dec 06 '18 at 00:46
  • I don't know what you're supposed to be calculating, so I can't say if what this does is wrong, or not. This is simply not how memoization works, or what it is all about. Read Wikipedia's article, if you want to learn how memoization is supposed to work. – Sam Varshavchik Dec 06 '18 at 01:00
  • Usually, you make your cache/memo global to your class or scope. When in recursion, if you change your subtree (in your case, calling the function in your for loop), then you will lose your cache that is created in the previous subtree (the previous iteration of your for loop). – votelessbubble Dec 06 '18 at 01:23
  • https://stackoverflow.com/a/28989589/1774667 might work. – Yakk - Adam Nevraumont Dec 06 '18 at 02:03
  • You are doing an expensive summarizer for 'a' ( which is even not initialized). *Cache* makes no sense there, since you can do `a + dond,,,` in the loop instead. For memoising you need a global lookup table for the result based on the values of the arguments. It makes no sence in this example at all, since you never call the function with the same set of arguments more than once – Serge Dec 06 '18 at 03:07

0 Answers0