java - 在java中将迭代函数转换为递归

Question

我想将此函数转换为递归形式，谁能帮帮我，thx那个功能就是解决这个东西

X=1+(1+2)*2+(1+2+3)*2^2+(1+2+3+4)*2^3+ . . . +(1+2+3+4+. . . +n)*2^(n-1) 

public static int calcX(int n) {
        int x=1;
        int tmp;
        for(int i = 1 ; i <= n-1;i++) {
            tmp=0;
            for(int j = 1 ; j <= i + 1;j++) {
                tmp+=j;
            }
            x+=tmp*Math.pow(2, i);
        }
        return x;
    }

我的尝试是递归的新手

public static int calcXrecu(int n,int tmp,int i,int j) {
        int x=1;
        if(i <= n-1) {
            if(j <= i) {
                calcXrecu(n,tmp+j,i,j+1);
            }
            else {
                x = (int) (tmp*Math.pow(2, i));
            }
        }
        else {
            x=1;
        }
            return x;
    }

Answer 1

你有一个和的序列，它们本身就是和。
n 项可以从 (n-1) 项派生，如下所示:

a(n) = a(n-1) + (1+2+3+....+n) * 2^(n-1)  [1]

这是递归公式，因为它通过前一项产生每一项。
现在您需要另一个公式(高中数学)来计算 1+2+3+....+n 的总和:

1+2+3+....+n = n * (n + 1) / 2  [2]

现在在 [1] 中使用 [2]:

a(n) = a(n-1) + n * (n + 1) * 2^(n-2)  [3] 

所以你有一个公式，你可以用它从前一个术语中推导出每个术语，这就是你的递归方法所需要的:

public static int calcXrecu(int n) {
    if (n == 1) return 1;
    return calcXrecu(n - 1) + n * (n + 1) * (int) Math.pow(2, n - 2);
}

这一行:

if (n == 1) return 1;

是递归的导出点。
请注意，Math.pow(2, n - 2) 需要转换为 int，因为它返回 Double。