C语言中递归求不同数的方法

Question

假设数组A:1,2,3,1,1,3。不同的整数应在数组B中：1,2,3。然后，函数应打印：[1,1][1,2][1,3][2,1][2,2][2,3][3,1][3,2][3,3]。

我试图解决不重复的整数问题，但没有递归

#include <iostream>
#include <algorithm>
using namespace std;
    
void uniqueNumber(int A[], int n, int B[], int &dimB ){
    sort(A, A+n);
    
    for( int i = 0; i < n; i++ ){
        if( A[i] == A[i+1] ){
            continue;
        }
        else {
            B[dimB++] = A[i];
        }
    }
}

但问题是我必须以递归的方式解决它，有什么想法吗？

Answer 1

递归只是另一种循环方式。它通常是一种干净的方法，尽管它通常不会像实际的那样优化或，而循环并且除了尾部递归算法之外，它可以通过堆栈内存，除非数据大小很小，或者算法是对数或更好。这是一种线性算法（遍历数组），所以我不喜欢递归用于真正的解决方案，尽管这是一个很好的学习练习。

重要的是，使用递归时要考虑以下几点：数据的结构，不变量是什么（也就是说，在递归发生时，可以依靠什么保持为真），以及何时应该停止（“基本”情况）。

当您递归“遍历”数据时，通常一次只查看一个元素或一小块数据，以逐步构建解决方案。

有时，您必须在开始递归之前直接处理一些特殊情况。这对于处理不属于递归所需不变量的情况是必要的，例如当没有足够的数据来满足数据的预期“形状”时。

给定您的界面：

void uniqueNumber(int A[], int n, int B[], int &dimB );

我们已经知道了一些事情。首先，这不是一个好的界面。：）数组不是函数的安全参数，很容易出错。其次，dimB是一个“out”参数，除非有必要，否则不支持它（因为我们可以将大小作为函数返回值返回）第三，我们不知道B的大小，但必须假设它至少与A一样大。（这是该接口的另一个安全问题。）

但假设函数签名是固定的，这就是我们必须处理的。那么我们想要什么呢？

目标：按排序顺序找到每个写入B的唯一数字，并更新dimB以告诉调用者有多少项目写入B。

所以基本上我们想这样做：

• 对数字进行排序
• 使用索引i迭代数组
  • 如果当前值（A[i]）与之前的值（A[i-1]）不同，则将当前值附加到B，并增加dimB
  • 不要从A[-1]

  上面的不变量是：

  • 对于任何索引i，其前面都有一个有效值
  • 索引是

  主要步骤将是：

  >

  否则我们的不变量就会满足：我们至少有一个元素。第一个元素保证不在B中，所以排序A，然后立即将A[0]添加到B中，然后开始递归。当A的大小正好为1时，也可以处理这种情况。递归将立即返回。

  通常，递归算法由两个函数编写：第一个函数处理特殊情况并进行其他设置，然后调用第二个函数进行递归工作，知道所有特殊情况都已处理。

  考虑到上述因素后，这里是uniqueNumbers函数：

  void uniqueNumber(int A[], int n, int B[], int &dimB ) {
      if (n > 0) {
          std::sort(A, A+n);
          B[dimB++] = A[0];
          detail::uniqueNumberRec(1, A, n, B, dimB);
      }
  }
  

  由于递归帮助函数不是直接调用的，而是实现细节，我把它放在细节命名空间中，这是记录用户不应该直接调用它的常见做法，它也有助于将混乱排除在全局命名空间之外。

  那么递归函数是做什么的呢？

  它采用当前索引和初始函数采用的参数，这是上述描述的直接结果：

  namespace detail {
  void uniqueNumberRec(int curIdx, int A[], int n, int B[], int &dimB ) {
  
      // Base case: stop when we reach the end
      if (curIdx == n) {
          return;
      }
  
      // if current element differs from previous, include it in answer
      if (A[curIdx] != A[curIdx-1]) {
          B[dimB++] = A[curIdx];
      }
  
      // recurse onto next element in sequence, so increment curIdx
      uniqueNumberRec(curIdx + 1, A, n, B, dimB);
  }
  } // namespace detail
  

  重要的是要注意传递到递归函数（从initail函数）的初始索引是1，而不是0，因为我们已经将第一个元素添加到输出中，所以已经过去了。

  只要我们知道反复调用的curIdx 1最终将达到n，我们就知道递归将取得进展并将终止。我们已经在第一个函数中验证了n为正。

  有几件事值得注意：

  • 如果n==0，我们什么都不做
  • 如果n==1，我们将A的唯一元素添加到B中，然后递归，但由于curIdx==1和n==1，递归立即停止
  • 如果n

  同样值得注意的是：代码中有一个bug：

      if( A[i] == A[i+1] ){
  

  如果i是A中的最后一项，则A[i 1]读取超出界限。这是不可接受的。这就是为什么我在确保有前一个之后，阅读了前一个。

  编译器资源管理器示例：https://godbolt.org/z/8z3cf5Tab

Answer 2

我可以提供你的问题的解决方案，使用算法深度优先搜索。

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
void showContentSet(std::set<int>& input)
{
    for(auto iterator=input.begin(); iterator!=input.end(); ++iterator)
    {
        std::cout<<*iterator<<", ";
    }
    return;
}
void dfs(int current, int previous, std::vector<int>& first, std::set<int>& second, std::vector<int>& visited)
{
    if(visited[current]==1)
    {
        return;
    }
    visited[current]=1;
    for(int next=(current+1); next<first.size(); ++next)
    {
        if(next==previous)
        {
            continue;
        }
        if(first[next]==first[current])
        {
            continue;
        }
        else
        {
            second.insert(first[current]);
            second.insert(first[next]);
        }
        dfs(next, current, first, second, visited);
    }
    if(current==0)
    {
        for(auto& item : second)
        {
            for(auto& itemSet : second)
            {
                std::cout<<"["<<item<<", "<<itemSet<<"]"<<", ";
            }
        }
    }
    return;
}
void solve()
{
    const int maximumSize=20;
    std::vector<int> visited(maximumSize, 0);
    std::vector<int> inputVector={1, 2, 3, 1, 1, 3};
    std::set<int> inputSet;
    dfs(0, -1, inputVector, inputSet, visited);
    return;
}
int main()
{
    solve();
    return 0;
}

结果如下：

[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3],