Recursion with loops (generating data)

Question

Hello I need to know if it is possible to do something like this with recursion and how? I want to be able to choose how many loops I want, for instance GenerateNumbers(x) where x is numbers of loops I have inside.

int a, b, c;
for (a = 0; a < 10; a++)
{
    printf("\n%d", a);
    for (b = 0; b < 10; b++)
    {
        printf("\n%d%d", a, b);
        for (c = 0; c < 10; c++)
        {
            printf("\n%d%d%d", a, b, c);
        }
    }
}

This is not possible with wirting code, but it should be possible with recursion, since each call generates a new loop. — Tamer Shlash, Mar 13 '11 at 19:45

score 1 · Answer 1 · edited May 23 '17 at 12:04

Something like this?

void PrintCombinations(unsigned int CombinationLength)
{
    int * state = calloc(CombinationLength, sizeof(*state));
    Recurse(state, CombinationLength, CombinationLength);
    free(state);
}

void Recurse(int State[], size_t StateSize, unsigned int Depth)
{
    if(Depth)
    {
        for(State[Depth-1]=0; State[Depth-1]<10; State[Depth-1]++)
            Recurse(State, StateSize, Depth-1);
    }
    else
    {
        putchar('\n');
        for(;StateSize; StateSize--)
            printf("%d",State[StateSize-1]);
    }
}

(notice: this is C code, since you used printf in your example; if it were C++ the state array would have to be wrapped in a smart pointer like std::auto_ptr or std::unique_ptr in C++0x)

Notice that you can emulate this kind of recursion also with iteration, see for example this other answer of mine.

score 1 · Accepted Answer · answered Mar 13 '11 at 20:04

#include <stdio.h>
#include <stdlib.h>



int GenerateNumbersHelper(int depth,int max_depth,int* data)
{
    int i;
    if(depth == 1 + max_depth)
        return 0;

    for(i=0;i<depth;i++)
    {
        printf("%i",data[i]);
    }
    printf("\n");
    for(i=0;i<10;i++)
    {
        data[depth]=i;
        GenerateNumbersHelper(depth+1,max_depth,data);
    }
    return 0;
}

int GenerateNumbers(int depth)
{
     int* data;
     data = malloc(sizeof(int)*depth);
     GenerateNumbersHelper(0,depth,data);
     free(data);
}

int main(void)
{
    GenerateNumbers(3);
}

score 0 · Answer 3 · answered Mar 13 '11 at 19:45

0

It is indeed possible. You need to use a stack structure or at the very least an array if there is an upper bound on x.

answered Mar 13 '11 at 19:45

E.Benoît

796
6
9

Of course, the stack structure can be the call stack itself (via recursive function calls). – In silico Mar 13 '11 at 19:48
No, it cannot, as the data from the previous calls need to be accessed in his case (e.g. the last printf in the OP's example uses all three loop iterators). Unless you're writing some ugly ASM-based hack to access the call stack. You could possibly do it with varargs too. – E.Benoît Mar 13 '11 at 19:50
@E.Benoît: You can pass arguments to function calls, no? I didn't say it'll be a pretty function, but I'd be surprised if it wasn't possible. – In silico Mar 13 '11 at 19:51
@in silico, errr, not in an arbitrary amount which is set itself by a parameter. See other answer. – E.Benoît Mar 13 '11 at 19:54
@E.Benoît: Right, but Matteo Italia was able to do it with function call recursion. So it is possible to use the call stack as the stack for recursion. – In silico Mar 13 '11 at 19:58
@In silico: I think that the point here is that it seems that you need an auxiliary data structure apart from the stack itself, since in the final step of the recursion you need to access the data of the external recursive calls. Actually you can make it work even without the fixed array of my solution, creating a sort of "linked-list" solution with variables on the stack and a parameter, but it would be much slower. – Matteo Italia Mar 13 '11 at 20:02
@in silico, I think we've been misunderstanding each other here. The "State" array associated with the "Depth" parameter Matteo Italia passes around is what I meant by a stack structure. – E.Benoît Mar 13 '11 at 20:03
@E.Benoît @Matteo Italia: Ah, I see what you mean now. – In silico Mar 13 '11 at 20:15

Recursion with loops (generating data)

3 Answers3