递归求和方法

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;

    }

我鼓励您使用您最喜欢的调试器逐步完成此过程，以说服自己就是这种情况。

* 警告：实际上，我们实际上不能使用它来生成任何自然数的总和，因为我们最终会遇到以下几个问题之一：

1. 有无数个自然数，但只有有限的内存量。（请注意，无穷本身不是自然数，甚至也不是实数，而是超实数）。

2. 最终，计算所需的时间长度将超过正常人的寿命。例如，计算 10^10 的总和将花费近 167 小时（即使您每秒执行一百万次操作）。以每秒 1000000 次操作计算 10^20 的总和将需要 190,258,751年（即超过 1.9亿年）。

3. 一个数字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