Wednesday 29 July 2015

Solve following function

value(n) =  n if (n < 12)
            = n/2 + n/3 + n/4 (else)

You can solve above program using recursion very easily. One problem in recursion is, it runs slow, because you are ending in calculating many times for same value.
Following program solves the problem using recursion and recursion with memory.

import java.util.*;

public class SumFunction {
 private static Map<Integer, Integer> map = new HashMap<>();

 public static int getRecursiveSumUsingMemory(int num) {
  if (num < 12)
   return num;

  if (map.containsKey(num)) {
   return map.get(num);
  }

  int sub1 = getRecursiveSumUsingMemory(num / 2);
  int sub2 = getRecursiveSumUsingMemory(num / 3);
  int sub3 = getRecursiveSumUsingMemory(num / 4);

  int sum = sub1 + sub2 + sub3;
  map.put(num, sum);
  return sum;
 }

 public static int getRecursiveSum(int num) {
  if (num < 12)
   return num;

  return getRecursiveSum(num / 2) + getRecursiveSum(num / 3)
    + getRecursiveSum(num / 4);
 }

}


No comments:

Post a Comment