递归toString方法

Question

我正在研究我目前的任务,即创建一个LinkedList数据结构,我已经创建了它以及其他方法,它工作得非常好.我的最后一个问题是制作一个toString方法.这应该是:

"toString方法返回列表的String表示.用逗号分隔每个项目,并将项目括在大括号中,例如{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

你想要这样的东西(给出递归的基本思想,不会起作用)

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

Answer 2

我认为从代码的角度来看，其他答案是合适的，但我只是想添加更多理论来帮助您了解如何实现这一目标。进行递归时，您总是需要两件事：基本情况和递归情况。基本情况是非常容易解决的问题，而递归情况是您如何逐步解决可解决的简单情况。

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

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

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)
}

希望这可以帮助您了解如何递归地解决这个问题。当然，如何让它发挥作用确实有很多变化。没有一种“正确”的递归方法，就像没有一种“正确”的方法来编写循环一样，但一般的“基本情况”和“递归情况”思维模型通常是最好的起点。