递归求和方法

Question

我不明白以下代码的结果如何6，当调用为时sum(3)。有人可以解释一下吗？

public int sum(int number) {

    if (number == 1) {

        return number;

    } else {

        return number + sum(number - 1);

    }

}

Answer 1

这样想：如果我告诉你sum以前的number，你能告诉我sum现在的number吗？如果我告诉你sum(4) = 10，那是sum(5)什么？嗯，很明显sum(5) = 5 + sum(4) = 5 + 10 = 15。这是另一个挑战：基于此，您能计算出sum(7)吗？好吧，很明显sum(7) = 7 + sum(6) = 7 + 6 + sum(5) = 7 + 6 + 15 = 28- 我们已经“知道”了 的值这一事实sum(5)意味着我们可以直接将其替换（至少为了我们手工计算的目的）。你知道了：如果我在序列中的某个地方给你一个任意数字，你就会知道序列中后面的值是如何与它相关的。然后，您可以使用它来生成更多值。碰巧的是，最初写这个的人给了我们序列中的第一个值：sum(1) = 1。这（至少在理论上）允许我们为任何自然数生成总和。*（见下面的警告）。顺便说一下，下面的for循环基本上是等价的：public static int forSum(int number)    {        int ret = 0;        for (int i = number; i >= 1; i--)        {            ret += i;        }        return ret;    }我鼓励您使用您最喜欢的调试器逐步完成此过程，以说服自己就是这种情况。* 警告：实际上，我们实际上不能使用它来生成任何自然数的总和，因为我们最终会遇到以下几个问题之一：有无数个自然数，但只有有限的内存量。（请注意，无穷本身不是自然数，甚至也不是实数，而是超实数）。最终，计算所需的时间长度将超过正常人的寿命。例如，计算 10^10 的总和将花费近 167 小时（即使您每秒执行一百万次操作）。以每秒 1000000 次操作计算 10^20 的总和将需要 190,258,751年（即超过 1.9亿年）。一个数字int能容纳多大是有严格限制的。然而，我们仍然有解决方案的数学规范：sum(10^20) = 10^20 + sum(10^20 - 1)- 我们只是没有时间计算它。

Answer 2

这叫做递归如果您将调试此代码，您将看到如下内容：step0: sum(3)step1: 3 + sum(2)step2: 3 + 2 + sum(1)step3: 3 + 2 + 1