将递归方法转换为公式

Question

这个查询对你们来说可能很简单，但我不知道为什么我已经抓耳挠腮地思考了两个小时。

下面是一个简单的代码，它通过相同的方法循环99次，结果将是5050。

class test {
    public static void main(String args[]) {
        test test1 = new test();
        System.out.println(test1.xyz(100));           
    } 
    public int xyz(int num) {
        if(num ==1) {
           return 1;        
        }  
        else {
           return(xyz(num-1) + num);
        }
    }
}

我的问题是如何手动解决这段代码。我需要使用哪个方程式？

- Manju

---

5050对于你的代码是正确的。你想让你的程序做什么？ - Sercan Ozdemir

我想知道如果我们想要手动计算，需要使用什么方程/公式。 - Manju

Answer 1

在你的递归函数xyz()中发生的情况是将100到1相加。

100 + 99 + 98 + .... + 1

这意味着将前 nth 个自然数相加！因此，您可以使用简单的公式来找到结果：

n(n + 1) / 2

在程序中：

n = input;
sum = n(n + 1) / 2

或者，如果你想循环求和，你可以这样做：

sum = 0;
for (i = 1; i <= input; i++)
    sum += i; // sum = sum + i

- mazhar islam

Answer 2

这个方程实际上是 f(n) = f(n-1) + n，当 n=1 时，f(n)=1。这实际上是所有数字的总和，当 n=100 时，结果为 (100*101)/2 = 5050，因为自然数的总和为：n(n+1) / 2。这种方法是递归的。

如果你想要迭代版本，那么你需要使用循环。例如：

public static void main(String[] args) {
        int result = 0;
        for (int i=0; i<=100; i++) {
            result = result + i;
        }
        System.out.println(result);
}

- akhil_mittal

Answer 3

你的程序的作用是将1到num之间的所有数字相加。在每次迭代中，你将num-1加到num上，因此它的计算方式类似于“100 + 99 + 98 + 97 ...”。

你要寻找的方程式是(N(N + 1))/2。

- Flickster

Answer 4

你可以使用“迭代法”或“代入法”来解决这个问题。这些方法通常用于计算时间复杂度，但也适用于你的目的。

基本上，你需要将你的方法写成一个数学函数。

T(n) = T(n-1) + n , n > 1
T(n) = 1          , n = 1

当您这样做时，可以迭代函数i步，其中i是一个随机数。有关更多信息，请查看此页面：

算法分析 - geeksforgeeks

- stuck

Answer 5

当你第一次调用 test1.xyz(100) 时，它会使用参数100调用xyz() 方法。然后它调用 return(xyz(num-1) + num);，意思是它调用xyz(99) 并将100添加到其中。因为xyz(99)尚未评估，所以它被推入堆栈。在调用xyz(99)时，它调用 return(xyz(num-1) + num);，意思是它调用xyz(98) 并在其中添加99。因为xyz(99)尚未评估，所以它被推入堆栈中。它不断将 xyz() 的调用压入堆栈，直到你调用xyz(1)+2。根据代码，xyz(1)返回1。因此，xyz(1)+2语句将结果3返回给调用 xyz(2)。现在编译器弹出已堆叠的调用，并最终返回结果。

- वरुण