项目欧拉(P14):递归问题

Question

嗨我正在项目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;
      }
   }

}

Answer 1

你的问题不是堆栈的大小(你已经记住了值),但是

1. 序列中某些数字的大小,和
2. 32位整数的上限.

暗示:

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

这应该是足够的:)

PS你会在很多项目的euler问题中遇到对BigNums的需求......