使用递归来求和数

Question

我刚刚研究了递归的概念,我想我会尝试一个简单的例子.在下面的代码中,我试图获取数字:1,2,3,4,5,并使用递归将它们一起添加.我预计结果为15,但我的代码返回16.

我究竟做错了什么？

码:

    static void Main(string[] args)
    {

        Console.WriteLine(Sum(5));
        Console.Read();
    }


    static int Sum(int value)
    {
        if (value > 0)
        {
          return value + Sum(value - 1);
        }
        else
        {
            return 1;
        }
    }

Answer 1

你在else子句中返回1.你应该返回0:

else
{
    return 0;
}

如果该值不大于零,为什么你会首先返回一个？

Answer 2

您的代码执行如下:

Sum --> 5
  Sum --> 4
    Sum --> 3
      Sum --> 2
        Sum --> 1
          Sum --> 0
          1 <---
        2 <---
      4 <---
    7 <---
  11 <---
16 <---

检查你的基础案例.

Answer 3

其他人已经注意到了错误,我将详细说明递归.

虽然C#目前不执行尾调用优化(尽管IL有特殊tail指令),但值得一提的是尾递归通常是一件好事.

尾递归是递归的一种特殊情况,其中函数的最后一个操作(尾调用)是递归调用.由于最后一次调用是递归调用,因此不需要保留调用函数的堆栈帧,并且编译器可以轻松地使用该信息来生成机器指令,使得堆栈根本不会增长.所以它基本上可以将递归函数转换为迭代函数.

重写代码以支持尾递归可以像下面这样完成:

static int Sum(int result, int value)
{
    if(value == 0)
        return result;

    return Sum(result + 1, value - 1);
}

Answer 4

static int Sum(int value)
{
    if (value > 0)
    {
        return value + Sum(value - 1);
    }
    else
    {
        return 0; //Change this.
    }
}

Answer 5

那是因为,当值为= 0时,返回1.然后它被添加.

Sum的"else"子句应该返回0.