c# - 递归如何打印列表的总和

Question

我正在尝试使用递归算法查找列表的总和

我正在学习递归算法，我知道我可以用另一种方式做到这一点，但我正在学习

这是我的代码(非常简单)

class SumList
{

    public SumList(int[] list ) {
        List<int> listInteger = new List<int>();
        for (int i = 0; i < list.Length; i++)
            listInteger.Add(list[i]);
        sum(listInteger);
    }


    private double sum(List<int> list) {
        if (list.Count == 1)
        {
            return list[0];
        }
        if(list.Count ==2)
        {
            Console.Write(printList(list));
            Console.WriteLine((list[0] + list[1]));
            return list[0] + list[1];
        }
        double last = list[list.Count - 1];
        List<int> backupList = new List<int>(list);
        list.RemoveAt(list.Count -1);
        double s = last + sum(list);
        Console.Write(printList(backupList));
        Console.WriteLine(s);
        return s;
    }
    private string printList(List<int> list)
    {
        string result = "";
        for (int i = 0; i < list.Count; i++)
        {
            result += list[i];
            if (i != list.Count - 1)
            {
                result +="+ ";
            }
            else
            {
                result+= " = ";
            }
        }
        return result;
    }
}

这样调用它:

int []listInt = new int[] { 4, 5, 6, 7, 9 , 10 };
            new SumList(listInt);
            Console.ReadLine();

我的问题是结果是:

我想要结果，但像这样:

4 + 5 + 6 + 7 = ...
4 + 5 + 6 = ...

所以结果应该向后打印

我再次知道有几百万种方法可以找到列表的总和，但我正在尝试学习递归算法

Answer 1

您可能知道，递归函数是调用自身的函数。这意味着，为了递归地解决问题，我们必须将问题分成多个步骤，这样步骤之间的过程不会改变，但函数的输入会改变。此外，如果我们的递归函数要正确终止，那么我们采取的每一步问题都必须变得“更小”。此步骤代表一个递归单元。此外，与“正常”迭代不同，我们提前不知道何时会到达问题的终点。因此，我们需要一种机制来确定问题何时结束并应该停止递归。这称为基本案例。

让我们尝试一下查找列表总和的示例。

我们必须做的第一件事是提出一个递归单元(一个抽象步骤，我们可以一遍又一遍地重复，直到找到解决方案)。

我们知道输入类型为 List<int>

在这种情况下，我们可以注意到(此处为伪代码)sum(list) == list[0] + sum(restOfList) 。请注意，现在我们有一个确定的值 ( list[0] ) 和一个 List<int> 类型的对象。 (即restOfList)。

所以，现在我们有了一个简洁的、可重复的过程。

//Idk what language you are using, or if it matters, but I am writing this in java
public int sum(List<Integer> list) {
  //still need a base case
  return  list.get(0) + sum(list.subList(1, list.size()));
} 

现在我们只需要确定基本情况。因此，我们需要确定何时遍历完列表中的所有元素。

为此，让我们执行几个步骤，看看会发生什么。让我们从以下列表开始:{1, 2, 3, 4}

sum({1, 2, 3, 4}) 
-> 1 + sum({2, 3, 4})
       -> 2 + sum({3, 4})
              -> 3 + sum({4})
                     -> 4 + oops!!!

显然，我们无法从大小为 1 的列表中获取从索引 1 开始的子列表。这为我们提供了基本情况的答案。

public int sum(List<Integer> list) {
  printList(list);
  //base case
  if (list.size() == 1)
    return list.get(0); //recall that this is the entire list
  //otherwise, continue to next step.
  return  list.get(0) + sum(list.subList(1, list.size()));
}

加法之所以有效，是因为第一步的 return 语句依赖于第二步的 return 语句，依此类推。这也是步骤将以相反顺序打印的原因。

为了清楚起见，让我们最后一次追溯它。

sum({1, 2, 3, 4}) //sum({1, 2, 3, 4}) is called from main()
-> 1 + sum({2, 3, 4}) //sum({2, 3, 4}) is called from sum({1, 2, 3, 4})
       -> 2 + sum({3, 4}) //sum({3, 4}) is called from sum({2, 3, 4})
              -> 3 + sum({4}) //sum({4}) is called from sum({3, 4})
                     <- 4 //sum({4}) returns 4 to sum({3, 4})
                 3 + 4
              <- 7 //sum({3, 4}) returns 7 to sum({2, 3, 4})
          2 + 7
       <- 9 //sum({2, 3, 4}) returns 9 to sum({1, 2, 3, 4}) 
   1 + 9
<- 10 //sum({1, 2, 3, 4}) returns 10

我希望这有助于让事情变得更清晰。