how to make a recursive counter-CodePudding

I'm trying to make a counter function that takes n as an argument so if n is 2 the result would be 01, 02, 03, ..., 99 and if n is 3 the result would be 001, 002, ..., 999 and so on I'm new to recursion and couldn't find a way to do it so I decided to make a solution for n = 2 then I'll try to generalize it
but unfortunately I couldn't. My solution for n = 2 is:

#include <stdio.h>

void    allPossibleComb(void)
{
    char    counter[2];

    counter[0] = '0';
    counter[1] = '0';
    while (counter[0] <= '9')
    {
        counter[1] = '0';
        while (counter[1] <= '9')
        {
            printf("%c%c ", counter[0], counter[1]);
            counter[1]  ;
        }
        counter[0]  ;
    }
}

int main(void) {
  allPossibleComb();
  return 0;
}

So for n = 2 I needed two while loops the conclusion I had if n = 9 I'll need 9 while loops and that pushed to think of a recursive solution

I made a lot of attemps but I just couldn't get it so here the code of my last attempt which won't make any sense but I'll just put it here

void recursive_counter(int n,int c, char seq[])
{
    
    if(seq[n] == '9'){
        seq[n] = 0;
        return;
    }

    while(seq[c] < '9')
    {
        seq[c]  ;
        print_sequence(seq);
    }
    recursive_counter(n, c 1, seq);
}

n is length of array, c supposed to be an index and seq is an array ['0', '0'].

How can I approach such recursive problems? Note: it's a task where I can't use for loops and I can't use integers

CodePudding user response：

You could do something like this to use recusion, and the while loop is short enough and constant length so if you really wanted to you could get rid of it. You should be able to call allPossibleComb(2) and get the same output as your working function.

void recursive(unsigned int n, const char* str, unsigned int length)
{
    if (!n) {
        // if n == 0 we are passed the final layer and should print
        printf("%s ", str);
        return;
    }
    
    // buffer for print
    char buffer[21];
    // copy the input string so we don't change it
    strcpy(buffer, str);
    // add the next digit   null terminator
    buffer[length] = '0'-1;
    buffer[length 1] = '\0';
    do {
        // increment digit in current layer and recurse
        buffer[length]  ;
        recursive(n - 1, buffer, length   1);
    } while (buffer[length] != '9'); // continue looping until we have done all digits '0' to '9'
}

// call recursive without having to put in initial values for some of the arguments
void allPossibleComb(unsigned int n)
{
    recursive(n, "", 0);
}

allPossibleComb doesn't do anything here but call recursive for you with the starting values for str and length

CodePudding user response：

Here is a generalized pure recursive solution, you can control the width by modifying the initial c in main:

#include <stdio.h>

void counter_recursive(char c[], int idx, int n);
void digit_recursive(char c[], int idx, int n, int digit);

char nums[] = { '1', '2', '3', '4', '5', '6', '7', '8', '9', '0' };

void digit_recursive(char c[], int idx, int n, int digit)
{
    if (digit >= sizeof(nums))
    {
        return;
    }

    counter_recursive(c, idx 1, n);
    c[idx] = nums[digit];
    digit_recursive(c, idx, n, digit 1); 
}

void counter_recursive(char c[], int idx, int n)
{
    if (idx >= n)
    {
        printf("%s ", c);
        return;
    }

    digit_recursive(c, idx, n, 0);
}

int main()
{
    char c[] = "000";
    counter_recursive(c, 0, sizeof(c)-1);
}

Note: it doesn't print commas and it prints zero at first.

CodePudding user response：

You have a good start. However, with problems that deal with recursion, I find it easiest to define two functions - the first is called from your main() or whoever's requesting the problem to be solved, and the second is a recursive helper. Let's modify your function definitions to meet this:

void allPossibleComb(const int n); // call from your main
void recursiveComb(???); // recursive helper

We know that the recursive generator should step through, incrementally some sort of array. So, right off the bat, two of the parameters to the helper should involve the array size n and sequence to be modified (which can be thought of as a pointer to a sequence).

Furthermore, it makes sense to fix the current element of the sequence and step through all possible combinations to the right of it. This gives us a third parameter - the current index/position into our sequence. So, the recursive helper might look like:

void recursiveComb(const int n, const int pos, char **p_seq); // recursive helper; keep track of last index, current position, and current sequence

Initially, we should have an array of '0' and start at the very left of the sequence, so this gives us an idea on how to initialize and call our recursive helper from allPossibleComb.

void allPossibleComb(const int n) {
    // set up sequence
    char *seq = malloc(sizeof(char) * (n   1));
    for(int i = 0; i < n; seq[i] = '0', i  );
    seq[n] = '\0';
    recursiveComb(n, 0, &seq);
    free(seq);
    return;
}

To start filling in recursiveComb, it makes sense that the recursion is done when pos hits n:

void recursiveComb(const int n, const int pos, char **p_seq) {
    if(pos == n) { // done
        // display *p_seq
        return;
    }
    ...

Since we want to generate all sequences, we should display the current one. In terms of the recursive helper, this is done by advancing pos without modifying the sequence in any way:

    recursiveComb(n, pos   1, p_seq); // keep current state and iterate

Lastly, we'd like to increment the current value in the sequence, if possible. This is also straightforward:

    if((*p_seq)[pos] != '9') { // can increment so do so
        (*p_seq)[pos]  ;

We need to not only display this sequence but also continue the process of incrementing then displaying. Fortunately, the recursive helper handles this completely. However, we still need to return to our initial state, so that recursive calls at the outer level are correct:

        recursiveComb(n, pos, p_seq); // recurse; this will display the updated sequence and increment again if needed
        (*p_seq)[pos]--; // restore state
    }

Putting it all together, the recursive helper looks like the below:

void recursiveComb(const int n, const int pos, char **p_seq) {
    if(pos == n) { // done
        // display *p_seq
        return;
    }
    
    recursiveComb(n, pos   1, p_seq); // keep current state and iterate
    // try incrementing current position
    if((*p_seq)[pos] != '9') { // can increment so do so
        (*p_seq)[pos]  ;
        recursiveComb(n, pos, p_seq); // recurse; this will display the updated sequence and increment again if needed
        (*p_seq)[pos]--; // restore state
    }
    
    return;
}

Finally, the entire program would look like this:

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

void allPossibleComb(const int n); // call from your main
void recursiveComb(const int n, const int pos, char **p_seq); // recursive helper; keep track of last index, current position, and current sequence
void printSequence(char **p_seq) {
    printf("%s\n", *p_seq);    
}

void allPossibleComb(const int n) {
    // set up sequence
    char *seq = malloc(sizeof(char) * (n   1));
    for(int i = 0; i < n; seq[i] = '0', i  );
    seq[n] = '\0';
    recursiveComb(n, 0, &seq);
    free(seq);
    return;
}

void recursiveComb(const int n, const int pos, char **p_seq) {
    if(pos == n) { // done
        printSequence(p_seq);
        return;
    }
    
    recursiveComb(n, pos   1, p_seq); // keep current state and iterate
    // try incrementing current position
    if((*p_seq)[pos] != '9') { // can increment so do so
        (*p_seq)[pos]  ;
        recursiveComb(n, pos, p_seq); // recurse; this will display the updated sequence and increment again if needed
        (*p_seq)[pos]--; // restore state
    }
    
    return;
}

int main() {
    printf("Doing combinations\n");
    allPossibleComb(3);
    printf("Done\n");
    return 0;
}