How to Print All N-digit Numbers Recursively in C?-CodePudding

I'm trying to print all N-digit numbers with a given phrase recursively (excluding 0).

For example, given input:

void rec_fun ( "Hello" , 2 )

My output would be:

Hello 11
Hello 12
Hello 13
Hello 14
Hello 15
...
Hello 21
Hello 22
Hello 23
Hello 24
...
Hello 96
Hello 97
Hello 98
Hello 99

Some hints that I had:

Use dynamic memory

loop would only be used once and in the Stop condition.

Given function is:

void rec_fun ( int char* , int num );

My try, which didn't work, but I'm posting to get some directions:

void rec_fun ( char* c , int num ){
    if (num == 0){
        printf("%s",c);
    }
     
    int flag = 1;
    if (num>0){
        while(flag){
            for(int i=1 ; i<num 1 ; i  ){
                printf("%d",i);
                rec_fun (c, num-1);
                printf("\n");
                flag = 0;
            }
        }
    }
}

Would love to get some help on this !

CodePudding user response：

Some hints That I had :

Use dynamic memory

loop would only be used once and in the Stop condition.

I don't see the value in these hints. This is a single-loop algorithm, so the loop can be replaced completely with recursion (but shouldn't be, other than placating contrived assignment requirements, because recursion is less efficient, harder to write in this case, and can blow the stack easily on linear algorithms in language implementations that don't support tail recursion--but we'll play along).

Dynamic memory isn't needed to count here and I'm not sure how that'd factor in.

A good hint would be something along the lines of: what's the base case, and how does the parameter num allow you to approach the base case on each call? If the initial call is rec_fun("Hello", 2), how do you know you should print 11 and stop at 99?

The bad way to solve the problem is to use global data, but unnecessarily shared state makes the function brittle, non-rentrant and hard to debug.

Better to use a separate helper function that does the actual recursion, accepting the current value of n and therefore lets you approach a base case.

After that, there's the detail of figuring out how to convert the number of digits to the actual digits. Exponents are the key: 10 ** (n - 1) for the start (inclusive) and 10 ** n for the stop (exclusiive), where ** is exponentiation.

#include <math.h>
#include <stdio.h>

void print_n_to_end_with_prefix_recursive(
    const char *prefix, const int n, const int end
) {
    if (n < end) {
        printf("%s %d\n", prefix, n);
        print_n_to_end_with_prefix_recursive(prefix, n   1, end);
    }
}
void print_n_digit_numbers_with_prefix(const char *prefix, const int n) {
    int start = pow(10, n - 1);
    int stop = pow(10, n);
    print_n_to_end_with_prefix_recursive(prefix, start, stop);
}

int main(void) {
    print_n_digit_numbers_with_prefix("Hello", 2);
    return 0;
}

If you want to exclude 10, 100, etc, then add 1 to start before kicking off the recursion for values of n > 1. You can also handle the 0-digit case specially if you want. The program will crash on large numbers of n, so some validation is recommended.

CodePudding user response：

This uses recursion to add 1 digit each level:

void rec_fun(char * str, int num, int num_digits)
{
    if (num_digits == 0) {
        printf("%s %d\n", str, num);
    } else {
        // Need more digits, so call recursively.
        for (int i = 1; i < 10; i  )
            rec_fun(str, num * 10   i, num_digits-1);
    }
}

int main(int argc, char const *argv[])
{
    rec_fun("Hello", 0, 2);
}

Output

Hello 11
Hello 12
Hello 13
Hello 14
Hello 15
...
Hello 99

CodePudding user response：

You can try following:

#include <stdio.h>
void helper(char * c, int num, int digits)
{
    if (digits) {
        int i = 1;
        while(i <= 9) {
            helper(c, num * 10   i, digits-1);
            i  ;
        }
    
    } else {
        printf("%s %d\n", c, num);
    }
}

void rec_fun(char * c, int num) {
    helper(c, 0, num);
}
int main()
{
    rec_fun("Hello", 2);
    return 0;
}

Time complexity: O(10^N) [N is num (for example, 2 in question)].

Space complexity: O(1) [No extra space needed, call stack for recursion is ignored]

Note: Recursion will not work after N becomes larger.