如何将递归方法提速至1秒内？禁止使用循环与流

需要用递归完成任务，代码得在普通电脑1秒内跑通，不能用for/while循环和流，但可以用辅助方法和变量。现在已经写出了递归实现，方法在-111 < n < 131范围内有效，但n超过30后就卡得不行。之前试过用数组缓存结果，但不确定这种方式算不算“全递归实现”，想问问怎么优化这个递归方法的性能。

附现有代码：

public static long sequence(int n, int a, int b, int c) {
   if (n > -111 && n < 131) {
      if(n==0) {
         return a;
      }
      if(n==1) {
         return b;
      }
      if(n==2) {
         return c;
      }
      if (n < 0) {
         return 2 * sequence(-n, a, b, c);
      } else {
         return sequence(n - 1, a, b, c) - sequence(n - 2, a, b, c) + 2 * sequence(n - 3, a, b, c);
      }
   }
   return 0L;
}

• 用记忆化缓存，完全符合全递归要求：你担心数组缓存违规其实没必要，缓存只是避免重复计算，核心逻辑还是递归，完全没问题。可以用HashMap当缓存，通过辅助递归方法来维护缓存，全程不用循环。比如每次计算前先查缓存，有结果直接返回，没有就递归计算后存到缓存里，这样能避免原代码里大量重复的递归调用（比如算sequence(5)时会反复算sequence(3)、sequence(2)），性能会暴涨，n到130也能秒出结果。
  改造后的代码示例：

  import java.util.HashMap;
  import java.util.Map;
  
  public class SequenceCalc {
      private static Map<Integer, Long> cache = new HashMap<>();
  
      public static long sequence(int n, int a, int b, int c) {
          // 初始化基础值到缓存，避免不同a/b/c参数互相干扰
          cache.clear();
          cache.put(0, (long)a);
          cache.put(1, (long)b);
          cache.put(2, (long)c);
          return recurse(n);
      }
  
      private static long recurse(int n) {
          if (n <= -111 || n >= 131) return 0L;
          if (cache.containsKey(n)) return cache.get(n);
          
          long res;
          if (n < 0) {
              res = 2 * recurse(-n);
          } else {
              res = recurse(n-1) - recurse(n-2) + 2 * recurse(n-3);
          }
          cache.put(n, res);
          return res;
      }
  }
  

• 试试尾递归优化（可选）：有些JVM支持尾递归优化，就是把递归写成尾调用形式，让JVM复用栈帧减少开销。不过Java官方JVM对这个优化不算彻底，所以还是记忆化缓存的效果更靠谱。

• 简化递推逻辑：可以试着推导下负数n的直接计算规则，不用递归调用正数n的结果，比如看看能不能找到n<0时的公式，这样能少一层递归，进一步提速。

内容的提问来源于stack exchange，提问作者user19293033