Jump to content

Recursive memoized function help


AshtonJones

Recommended Posts

Hello, I'm struggling with constructing a momoized recursive function in C#
What I want is to find the sum of squares for n numbers.
What I want to memoize is an already found result of a number squared.
So in n numbers, if I have 3 instances of 2, I want to store (2*2)=4 and not call the function
recursively again to calculate (2*2), just return 4 and added it the sum. My function is below.
 
In playing around wiht the function, what keeps happening is that mem.Add(arr[index], calc); gives
me an exception saying key already exists in mem collection or it does not cycle through all
values in the array. Is this possible, and if so how?

            int total = 16;
            Hashtable mem = new Hashtable();

            int[] arr = new int[7];
            arr[0] = 2;
            arr[1] = 3;
            arr[2] = 2;
            arr[3] = 4;
            arr[4] = 3;
            arr[5] = 2;
            arr[6] = 4;

            var result = doSum(arr, mem, arr.Length - 1);

  public int doSum(int[] arr, Hashtable mem, int index)
  {
      int sum = 0;

      if (index < 0)
          return 0;
      if (mem.ContainsKey(arr[index]))
          return (int)mem[arr[index]];
      else
          calc = doSum(arr, mem, index - 1) + (int)Math.Round(Math.Pow(arr[index], 2));

      mem.Add(arr[index], calc);

      return sum;
  }

Link to comment
Share on other sites

public int doSum(int[] arr, Hashtable mem, int index)
{
  int sum = 0;

  if (index < 0)
    return 0;

   int sqVal;
   if (mem.ContainsKey(arr[index]))
     sqVal = (int)mem[arr[index]];
   else
   {
     sqVal = (int)Math.Round(Math.Pow(arr[index], 2));
     mem.Add(arr[index], sqVal);
   }

   sum = doSum(arr, mem, index - 1) + sqVal;
   return sum;
 }
Link to comment
Share on other sites

On 3/12/2019 at 2:40 PM, AshtonJones said:

sqVal = (int)Math.Round(Math.Pow(arr[index], 2));

Isn't the same but easier? (without conversion from integer to float, and float to integer)

sqVal = arr[index] * arr[index];

 

 

The easiest would be to use debugger. Compile in debug mode, set break point, and start debugging with real-time observation of variables and arrays to check what values are read/written/calculated.

Old-school way to debug is by printing variables to e.g. console. You will see what happens step-by-step.

 

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.