So, Let say array A : 1,2,3,1,1,3 .The distinct integer should be in array B : 1,2,3. Then, the function should print: [1,1][1,2][1,3][2,1][2,2][2,3][3,1][3,2][3,3].

I tried to solve the distinct integer problem, but without recursive

#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];
        }
    }
}

But the problem is I have to solved it in recursive way, is there any idea ?

CodePudding user response：

I can offer the solution of your problem, using the algorithm Depth first search.

#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;
}

Here is the result:

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

CodePudding user response：

Recursion is just another way to loop. It's often a clean approach, though it generally does not optimize as well as actual for or while loops and except for tail-recursive algorithms, it can blow through stack memory unless the data size is small, or the algorithm is logarithmic or better. This is a linear algorithm (walking an array), so I don't like recursion for the real solution, though it's a good learning exercise.

The important thing is to think about with recusion are the following: the structure of your data, what invariants are (that is, what you can rely on to remain true while your recursion occurs), and when it should stop (the "base" case).

While you recurse "through" your data, you are usually looking at one element at a time, or a small chunk of the data, to incrementally build up a solution.

Sometimes you have to handle a few special cases directly before starting the recursion. This is necessary to handle cases that fall outside the invariants that your recursion requires, like when there isn't enough data to fulfill the expected "shape" of your data.

Given your interface:

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

We already know a few things. First, it's not a good interface. :) Arrays are not safe arguments to functions, and are highly error prone. Second, dimB is an "out" parameter, which is frowned upon except when it is necessary (since we could return the size as the function return value.) Third, we do not know the size of B, but must assume it is at least as large as A. (That is yet another safety issue with this interface.)

But assuming that function signature is fixed, it's what we have to work with. So what do we want?

GOAL: find each unique number, in sorted order, written into B, and dimB is updated to tell the caller how many items were written into B.

So basically we want to do this:

1. sort the numbers
2. iterate the array, using an index i
   • if the current value (A[i]) differs from the previous value (A[i-1]), append the current value to B, and increment dimB
   • do not read from A[-1]
3. increment i
4. when index i == n, we stop

The invariants from above are:

• for any index i, there is a valid value before it
• index i is > 0 and <= n
• each recursive call, i increases

The major steps will be:

1. If there is no work to do (A is empty), we are already done. Just return.

2. Otherwise our invariants are met: we have at least one element. The first element is guaranteed to not be in B, so sort A then add A[0] to B immediately, and then we begin our recursion. This handles the case when size of A is exactly 1, too. The recursion will simply return immediately.

Oftentimes, a recursive algorithm is written in two functions: the first handles special cases and does other setup, and then calls into the second function which does the recursive work, knowing all the special cases are already handled.

So here is the uniqueNumbers function after the above is considered:

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

Since the recursive helper function is not to be called directly, but is implementation detail, I put it in the detail namespace, which is a common thing to do to document that users shouldn't call it directly, and it also helps keep clutter out of the global namespace.

So what does the recursive function do?

It takes the current index and the same arguments that the initial function takes, and is pretty straight forward fallout of the description above:

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

It's important to notice that the initial index passed into the recursive function (from the initail function) is 1, not 0, because we already added the first element to the output, and so are already past that.

As long as we know that curIdx 1 repeatedly called will eventually reach n, we know the recursion makes progress and will terminate. We already have verified n is positive in the first function.

A few things worth noting:

• if n == 0 we do nothing
• if n == 1, we add the only element of A into B, then recurse, but the recursion immediately stops since curIdx == 1 and n == 1
• if n > 1, we add the first element of (sorted) A, and then recurse. So A[0] is already in the result, and we start recursion on A[1], knowing that A[i-1] (that is, A[0]) is a valid element to read. Then we recurse until our index is at n, which means we are done.

Also worth noting: In your code you have a bug:

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

If i is the last item in A, then A[i 1] reads out of bounds. This is not acceptable. That is why I read from previous, after ensuring that there is a previous.

Example on Compiler Explorer: https://godbolt.org/z/8z3cf5Tab