递归toString方法

Question

我正在处理我当前的任务，即创建一个LinkedList数据结构，我已经创建了它以及其他方法，它工作得非常好。我正在处理我的最后一个问题，即制作一个toString方法。它应该：

toString方法返回列表的字符串表示形式。用逗号分隔每个项目，并用大括号括住这些项目，例如{1,4,7,5}。公共toString方法必须调用私有递归方法来生成以逗号分隔的项目列表。（但您可以在公共方法中添加大括号。）

我让我的公共toString方法工作；

    public String toString() {
    int size = getSize();
    String str = "{ ";
    Link current = first;

    for(int i = 0; i < getSize(); i++, current = current.next) {
        str += current.getiData() + " ";
    }

    str += " }";
    return str;
}

（我知道我应该使用StringBuilder，只是暂时使用=。）但是对于私有方法，我甚至不知道要写它。现在我能想到的唯一方法是：

private String toString(int x) {
    if(i > 0) {
        toString(--x);
    }
    return ", ";
}

这是愚蠢的（真的不是递归），有人能澄清应该做什么，和/或给出伪代码吗？

Answer 1

这有点奇怪，因为toString方法的签名没有参数，这意味着需要另一种方法。在链表中，每个节点都有数据和指向下一个节点的指针。

public String getData(Node n, String value)
{
     if(n == null)
     {
         // We know we're at the end, so don't proceed.
         return value;
     }
     else
     {
         // n isn't empty, and ignoring the lack of stringbuilder
         value += n.getData();
         // Make a recursive call with the next value in the list, and the new string.
         return getData(n.next(), value);
     }
}

Answer 2

您想要这样的东西（给出了递归的基本思想，但行不通）

privat String toString(Link link) {
  if (link.isLast()) {
    return link.value();
  }
  else {
    return link.value() + toString(link.next());
  }
}

Answer 3

我认为从代码的角度来看，其他答案是合适的，但我只是想添加更多的理论来帮助您理解如何到达那里。在进行递归时，您总是需要两件事：基本情况和递归情况。基本情况是非常简单的解决方案，递归情况是您如何解决可解决的简单情况。

链表本身就是一种递归数据结构。例如，如果有一个包含10个项目的链接列表，则可以将其作为一个节点，并将包含9个项目的链接列表附加到该节点。

因此，对于基本情况（再次借用@Chris的答案），执行toString（）的最简单列表是一个空列表。所以你的基本情况看起来像这样（伪代码）：

if(list is empty)
{
   return "";
}

那么，递归案例需要使用现有的链表，并尝试向下处理基本案例。做到这一点最简单的方法是，从你知道你能解决的问题中分离出一小块，解决它，然后处理剩下的稍微小一些的问题。在打印链接列表的情况下，这意味着您可以从列表中获取一个项目，将其转换为字符串，然后再考虑列表的其余部分。因此，您的递归案例将如下所示（伪代码）：

if(list is not empty)
{
   String x = take the current node and translate it to a string;

   Add x to your running value of the String value of the entire list

   Recursively call this function with the next node in the list
   (you reduce your list size by 1 with each call and work down to your base case of an empty list)
}

希望这能帮助您理解如何递归地找到这个问题的解决方案。当然，在如何使其发挥作用方面有很多变化；没有一种“正确”的递归方式，就像没有一种“正确”的循环编写方式一样，但一般的“基本情况”和“递归情况”思维模式通常是最好的起点。