Sign in to follow this  
AshtonJones

Recursive memoized function help

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;
  }

Share this post


Link to post
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;
 }

Share this post


Link to post
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.

 

Share this post


Link to post
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
Sign in to follow this