c++ - 嵌套循环到尾递归

Question

实现:

bool no_uniq(list_t l);
//E: Returns true if l has no elements that appear only once in l; returns false otherwise
//Ex1: (1,5,1,5,1) -> True
//Ex2: (1,5,1,1) -> False

已经实现的功能:

bool list_isEmpty(list_t list); //True if the list is empty, false otherwise
list_t list_make(); //Make an empty list
list_t list_make(int elt, list_t list); //Make a list with element elt followed by list
int list_first(list_t list); //Retrieve the first element of list
list_t list_rest(list_t list); //Retrieve all elements of list besides the first one

所以我希望能够以尾递归方式处理这个问题，但我很难思考如何将通常具有的嵌套循环转换为尾递归函数。我知道一个尾递归调用应该处理“外部”循环，一个应该处理“内部”循环，但将它们放在一起解决这个问题似乎几乎是不可能的。任何帮助将不胜感激。

Answer 1

没有看到太多的代码，我会说

bool no_uniq(const list_t& list)
{
  if(list_empty(list))
      return true;      
  return no_uniq_acc(list_first(list), list_rest(list));
}

bool no_uniq_acc(int acc, const list_t& list)
{
  if(list_empty(list))
      return true;
  const int first = list_first(list);
  if(first==acc)
    return false;
  else
    return no_uniq_acc(first, list_rest(list));
}

如果我怀疑它是 c，您可以将 const list_t& 更改为 list_t。