java - 欧拉计画(P14): recursion problems

嗨，我正在做Euler项目中的Collat​​z序列问题(问题14)。我的代码适用于低于100000的数字，但具有更大的数字，则会出现堆栈溢出错误。

有没有一种方法可以重构代码以使用尾部递归，或防止堆栈溢出。代码如下:

import java.util.*;

public class v4
{

   // use a HashMap to store computed number, and chain size

   static HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

   public static void main(String[] args)
   {

      hm.put(1, 1);

      final int CEILING_MAX=Integer.parseInt(args[0]);
      int len=1;
      int max_count=1;
      int max_seed=1;

      for(int i=2; i<CEILING_MAX; i++)
      {
          len = seqCount(i);

          if(len > max_count)
          {
             max_count = len;
             max_seed = i;
          }
      }
      System.out.println(max_seed+"\t"+max_count);
   }

   // find the size of the hailstone sequence for N

   public static int seqCount(int n)
   {

      if(hm.get(n) != null)
      {
         return hm.get(n);
      }

      if(n ==1)
      {
         return 1;
      }
      else
      {
         int length = 1 + seqCount(nextSeq(n));
         hm.put(n, length);
         return length;
      }
   }

   // Find the next element in the sequence

   public static int nextSeq(int n)
   {

      if(n%2 == 0)
      {
         return n/2;
      }
      else
      {
         return n*3+1;
      }
   }

}

最佳答案

您的问题不在于堆栈的大小(您已经在记住值)，而是

序列中一些数字的大小，以及

32位整数的上限。

暗示:

public static int seqCount(int n)
{
   if(hm.get(n) != null) {
       return hm.get(n);
   }
   if (n < 1) {
      // this should never happen, right? ;)
   } ...
   ...

希望应该足够了:)

P.S.您会在很多项目欧拉问题中遇到对BigNums的需求...