how to make a recursive counter

Question

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

Answer 1

My two cents (without recursion):

#include <stdio.h>
#include <string.h>

void all_possible_comb (unsigned int digits) {

    if (digits == 0) return;

    /*  As we are dealing with a fixed-length string we use `fwrite()`
        instead of `printf()`; that allows to avoid adding a NUL
        terminator to `output_buffer`.  */

    char output_buffer[digits];
    unsigned int cursor = 0;

set_to_zero:
    memset(output_buffer + cursor, '0', digits - cursor);

print_number:
    fwrite(output_buffer, 1, digits, stdout);
    putchar('\n');
    cursor = digits;

next_digit:
    if (cursor < 1) return;
    if (output_buffer[--cursor] > '8') goto next_digit;
    output_buffer[cursor]++;
    if (++cursor < digits) goto set_to_zero;
    goto print_number;

}

int main (const int argc, const char * const * const argv) {

    all_possible_comb(3);
    return 0;

}

Or, alternatively, by using the heap and a completely different approach (still no recursion):

#define _GNU_SOURCE

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

static void all_possible_comb (unsigned int digits) {

    char * format;

    if (asprintf(&format, "%%0%ulu\n", digits) == -1) {

        fprintf(stderr, "Not enough memory\n");
        return;

    }

    long unsigned int limit = 1;

    for (
        unsigned int idx = 0;
            idx < digits;
        limit *= 10, idx++
    );

    for (
        long unsigned int count = 0;
            count < limit;
        printf(format, count++)
    );

    free(format);

}

int main (const int argc, const char * const * const argv) {

    all_possible_comb(2);
    return 0;

}

As you might have guessed, I hate recursive functions.

Answer 2

Since some people already answered I will try to show you how to do it and how to think on the solution.

as I told you in the comment, the most important thing to do is to define exactly what your recursion function gets and what it does. that's the hardest part, you need to think on something that will work for you best, lets look on the following defintion:

function inputs:

num of digits - how many digits i want.

last number - what is the last number i want to print.

what it does? - print all the numbers until the last number with zeroes if needed to fit the num of digits.

on what we do the recursion? - on the last number

so after we have all the defintion, lets solve it as an induction.

base: last number = 1, can we solve it? sure, just print 1 with numbers of zeroes needed.

step: lets say we know how to solve it for last_num -1 can we solve it or last_num? sure, we first print comma, and then we just need to print the last num with the numbers of zeroes needed.(i truly assume that it worked for last_num-1, that's the catch)

if you got it until here, you just need to code it and understand how to code every step of the induction.

since you got already some solutions i will post my code here:

#include <stdio.h>

int get_num_digits(int num)
{
    int digits = 0;
    while(num != 0)
    {
        num = num/10;
        digits++;
    }
    return digits;
}

void print_with_zeroes(int digits, int num)
{
    int num_digits = get_num_digits(num);
    int num_zeroes = digits - num_digits;
    while(num_zeroes > 0)
    {
        printf("0");
        num_zeroes--;
    }
    printf("%d", num);
}

void rec(int digits, int last_num_to_print)
{
    if(last_num_to_print == 1)
    {
        print_with_zeroes(digits, last_num_to_print);
    }
    else
    {
        rec(digits, last_num_to_print - 1);
        printf(",");
        print_with_zeroes(digits, last_num_to_print);
    }
}

int main()
{
    rec(2, 99);//just call to the function with the right parameters

    return 0;
}

Answer 3

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.