如何制作递归计数器

Question

我正在尝试创建一个以 n 作为参数的计数器函数所以如果 n 是 2 结果将是 01, 02, 03, ..., 99 如果 n 是 3，结果将是 001, 002, ..., 999 等等我是递归的新手，找不到实现它的方法，所以我决定为 n = 2 制定一个解决方案，然后我将尝试概括它
但不幸的是我做不到。我对 n = 2 的解决方案是：

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

所以对于 n = 2 我需要两个 while 循环我得到的结论是 n = 9 我需要 9 个 while 循环并推动思考递归解决方案

我尝试了很多次，但就是无法得到它，所以这里是我上次尝试的代码，它没有任何意义，但我会把它放在这里

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 是数组的长度，c 应该是一个索引，seq 是一个数组 ['0', '0'].

如何解决此类递归问题？注意：这是一个我不能使用循环并且不能使用整数的任务

Answer 1

你可以做这样的事情来使用 recusion，while 循环足够短而且长度恒定，所以如果你真的想要你可以去掉它。您应该能够调用 allPossibleComb(2) 并获得与您的工作函数相同的输出。

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] = '[=10=]';
    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 在这里什么都不做，只是用 str 和 length

的起始值为你调用 recursive

Answer 2

这里是一个广义的纯递归解决方案，可以通过修改main中的初始c来控制宽度：

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

注意：它不打印逗号，而是首先打印零。

Answer 3

我的两分钱（没有递归）：

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

}

或者，或者，通过使用堆和完全不同的方法（仍然没有递归）：

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

}

你可能已经猜到了，我讨厌递归函数。

Answer 4

既然已经有人回答了，我会尝试向您展示如何做以及如何思考解决方案。

正如我在评论中告诉你的那样，最重要的事情是准确定义你的递归函数得到什么以及它做什么。这是最难的部分，你需要考虑最适合你的东西，让我们看看以下定义：

函数输入：

位数 - 我想要多少位数。

最后一个数字 - 我要打印的最后一个数字是多少。

它有什么作用？ - 打印所有数字，直到最后一个数字为零，如果需要以适应位数。

我们在做什么递归？ - 最后一个数字

所以在我们有了所有的定义之后，让我们用归纳法来解决它。

base: last number = 1，我们能解决吗？当然，只需打印 1 和所需的零个数。

步骤：假设我们知道如何解决 last_num -1 我们可以解决它还是 last_num？当然，我们首先打印逗号，然后我们只需要打印最后一个 num 和所需的零数。（我真的假设它适用于 last_num-1，这就是问题所在）

如果你到这里为止，你只需要编写代码并了解如何编写归纳的每一步。

既然你已经有了一些解决方案，我会 post 我的代码在这里：

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

如何制作递归计数器

how to make a recursive counter

c

recursion

counter