C++ Function Calling Itself

Question

Question
I wish to know if this is a viable way to implement variable depth recursion so that I can run a function at each step and any better/other solutions to the description problem.
Description
Suppose I wish to have a function that fills an array either in pattern
x,y,x,y,x,ywhere x and y are variables defined by some algorithm
and x,y,z,x,y,z where x, y and z are variables defined by the same algorithm.

This should continue for all number of variables. Is this a viable way to implement it.

void recurse_n(int n)
{
    while(n > 0)
    {
        --n;
        recurse_n(n);
        n = 0;
        // Use algorithm here
    }
}

EDIT: Removed the incorrect return type previously referred to. Brainfart.

Answer 1

I'm a little unclear on the question, but it sounds like you have a set of variables a, b, c, ..., z and you want to fill an array so it contains a, b, c, ..., z, a, b, c, ..., z, a, .... If so, it's probably simplest to put the source variables in their own one-pass array a, b, c, ..., z and memcpy it to the destination array until it's filled

#define NUM 3
int a, b, c; // source variables
void fill(int* arr, unsigned int size) {
    int src[] = {a, b, c};
    unsigned int i;
    for(i = 0; i < size / NUM; i++)
        memcpy(arr + (NUM * i), src, sizeof(int) * NUM);
    memcpy(arr + (NUM * i), src, sizeof(int) * (size % NUM));
}

Answer 2

I do not think this is a viable way to do it, since: Let T(n) denote the running time of your function (dependent on input parameter n).

The base case n=0 yields following running time: T(0)=c, i.e. some constant runtime c.

Now you can define a recursive formula for the running time where n>0: T(n)=sum(i = 0 to n-1: T(i)).

If you solve this equation you get that T(n)=O(2^n), which means that your algorithm is exponential, which means that it is not tractable in practice.

Answer 3

So, based on your comment you want to know the best way to set up a recursive function. What you have done will work, but it is convoluted and slightly confusing. What I would do to simplify it is:

void recurse_n(int n) {
    if (n <= 0) {
        // Break-out condition
        return;
    }

    --n;
    recurse_n(n);

    // Your algorithm stuff here.
}

That will make it easier to see what is going on. One thing I would add though is that you might want to do the algorithm stuff before the call to recurse_n, but that all depends on what your algorithm is doing.

If you think about it, the way I have written it, it will recurse until n is less than or equal to 0 before doing any of the algorithm work. It might be that you want to do the algorithm work then recurse.

Answer 4

First of all, use a std::vector and a loop (I'm assuming x(), y() and z() return the ints you need, you could also use a vector there to store the values):

void fill( std::vector<int> &vec, std::vector<int> &values )
{
    size_t nValues = values.size();
    size_t sz = vec.size();
    for( size_t i=0; i<sz; i=i+nValues )
    {
        for( size_t j=0; j<nValues; ++j )
        {
            vec[i] = values[j];
        }
    }
}

int main()
{
    std::vector<int> vec;
    std::vector<int> values;
    /* fill values vector here */
    vec.resize( 512 ); // (arbitraty) size you need
    fill( vec, values );

    return 0;
}

This is more C++-ish and much faster than a recursive function. Also: store x, y, and z values so that the corresponding algorithm only executes once.

Answer 5

JimDaniel is right, the recursion here is an overkill. You're not returning anything from the function and it looks like you're only using "n" to control the number of recursions. Using a simple for-loop would be much clearer + more efficient.

Answer 6

Recursion to fill an array is a valid (even the best) option if your algorithm meets these requirements:

1. The value at position n depends on the values of at least some of the values that came before it
2. There is no (known) way to determine the value at position n without first determining the earlier values that it depends on.

An example that fits these requirements are the fibonacci numbers. Because you can't determine the n-th number without first determining all earlier numbers (though some shortcuts exist).

An example that doesn't fit these requirements is an array that is filled with the square of the index, where the value at position n is just n^2.

Finally, I'd suggest you rewrite your function according to the pattern in DaveJohnston's answer to your question if possible.