把递归转化为非递归函数

Question

运行一个java程序的时候遇到stackoverflow 错误，问题出在一个digamma函数，这是一个递归函数，我把xss调整为20M后运行还是有这个错误，所以我想把这个函数改写为非递归的，但是不知道怎么改，有高手可以给点提示不,任何建议都可以
代码是这样的public static double digamma(double x) {
if (x >= 0 && x < GAMMA_MINX) {
x = GAMMA_MINX;
}
if (x < DIGAMMA_MINNEGX) {
return digamma(DIGAMMA_MINNEGX + GAMMA_MINX);
}
if (x > 0 && x <= S_LIMIT) {
return -GAMMA - 1 / x;
} if (x >= C_LIMIT) {
double inv = 1 / (x * x);
return Math.log(x) - 0.5 / x - inv
* ((1.0 / 12) + inv * (1.0 / 120 - inv / 252));
}
return digamma(x + 1) - 1 / x;
}
下面是一些常量的定义：double GAMMA = 0.577215664901532860606512090082;
double GAMMA_MINX = 1.e-12;
double DIGAMMA_MINNEGX = -1250;
double C_LIMIT = 49;
double S_LIMIT = 1e-5;
递归JavaStack Overflow

Answer 1

if (x < DIGAMMA_MINNEGX) {            
    return digamma(DIGAMMA_MINNEGX + GAMMA_MINX);        
}这步不太好吧,x小于-1250,每次都加1.e-12   
如果x是个很小的数,那要加多少次啊?
不知道为什么要加一个这么小的数.考虑下是不是换个大点的.

Answer 2

其实这个函数是计算gamma函数的对数的导数，具体的计算过程我也不怎么清楚，也许是为了精确度什么的，谢谢你的回复

Answer 3

digamma(DIGAMMA_MINNEGX + GAMMA_MINX)
这个是一个常数，可以直接拿来用，我假设是DIG_C那就剩下最后一句是递归了。这个递归的规律是，把x+1的结果减去1/x。假设调用函数时x=1，总共调用了3次，那么展开就是：
digamma(1) = digamma(2) - 1/1
digamma(1) = (digamma(3) - 1/2) - 1/1找到规律，总是最后一次调用的返回值，减去1/x减去2/x...
数学一点，假设函数被调用了N次，x=1，那么就有：
digamma(1) = digamma(N) - 1 / (N-1) - 1 / (N-2)... - 2/1 - 1;综上所述，只要算出digamma(N)，就搞定了。代码：  public static double GAMMA = 0.577215664901532860606512090082;
  public static double GAMMA_MINX = 1.e-12;
  public static double DIGAMMA_MINNEGX = -1250;
  public static double C_LIMIT = 49;
  public static double S_LIMIT = 1e-5;
  public static double DIG_C = digamma(DIGAMMA_MINNEGX + GAMMA_MINX);  public static double digamma2(double x) {
    double iter = x;    int i;
    for (i = 0; true; i++) {
      if (iter >= 0 && iter < GAMMA_MINX) {
        iter = GAMMA_MINX;
      }
      if (iter < DIGAMMA_MINNEGX) {
        iter = DIG_C;
        break;
      }
      if (x > 0 && x <= S_LIMIT) {
        iter = -GAMMA - 1 / iter;
        break;
      }      if (iter >= C_LIMIT) {
        double inv = 1 / (iter * iter);
        iter = Math.log(iter) - 0.5 / iter - inv * ((1.0 / 12) + inv * (1.0 / 120 - inv / 252));
        break;
      }      iter += 1;
    }    for (; i > 0; i--) {
      iter -= 1 / (x + i - 1);
    }    return iter;
  }

Answer 4

digamma1和digamma2在算法上是和原始diagamma等价的，但由于计算顺序不同，diagamma2和原始的diagamma有误差，digamma1是和原始dagamma完全一样的。    static final ThreadLocal<double[]> temp = new ThreadLocal<double[]>()
{
@Override
protected double[] initialValue() {
return new double[1500];
}
};
public static double digamma1(double x) {
double[] ar = temp.get();
int subs = 0;
for(;;)
{
if (x >= 0 && x < GAMMA_MINX) {
x = GAMMA_MINX;
}
if (x < DIGAMMA_MINNEGX) {
x = DIGAMMA_MINNEGX + GAMMA_MINX;
continue;
}
if (x > 0 && x <= S_LIMIT) {
x = (-GAMMA - 1 / x);
break;
}
if (x >= C_LIMIT) {
double inv = 1 / (x * x);
x = (Math.log(x) - 0.5 / x - inv
* ((1.0 / 12) + inv * (1.0 / 120 - inv / 252)));
break;
}
ar[subs++] = 1/x;
x = x+1;
}
while(subs>0)
x -= ar[--subs];
return x;
}
public static double digamma2(double x) {
double subs = 0;
for(;;)
{
if (x >= 0 && x < GAMMA_MINX) {
x = GAMMA_MINX;
}
if (x < DIGAMMA_MINNEGX) {
x = DIGAMMA_MINNEGX + GAMMA_MINX;
continue;
}
if (x > 0 && x <= S_LIMIT) {
x = (-GAMMA - 1 / x);
break;
}
if (x >= C_LIMIT) {
double inv = 1 / (x * x);
x = (Math.log(x) - 0.5 / x - inv
* ((1.0 / 12) + inv * (1.0 / 120 - inv / 252)));
break;
}
subs += 1/x;
x = x+1;
}
return x-subs;
}