-1

I am finding all of Combinations, nC r :

#include <stdio.h>

void make_combination( int n, int r ){
    for (int x=1; x<n-r+1+1; x++){ 
        // because it is start from 1, add 1 to range, too
        for (int y=x+1; y<n-r+y+1; y++){
            for (int z=y+1; z<n-r+z+1; z++){
                printf("%d %d %d\n",x,y,z);            
            }
        }
    }
}

int main(void){
    int n, r;

    printf("Insert n : ");
    scanf("%d", &n);

    printf("Insert r : ");
    scanf("%d", &r);

    make_combination(n, r);
    return 0;
}

I want to make this to recursive function, to make it work on variable 'r' value, because I don't want fixed number of for loops.

I tried but couldn't make recursive function.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Jaeman Lee
  • 25
  • 3
  • "I want to make this to recursive function." Why? Recursion is often a less favourable solution. – Cheatah Sep 15 '21 at 12:50
  • 3
    If you want to make it a recursive function, show your attempt. i.e. include the function that you've tried, then explain what went wrong. An example (and many more) of _how_ to do is [here](https://stackoverflow.com/a/24495262/645128) – ryyker Sep 15 '21 at 12:52
  • The fundamentals of making a recursive function are found in the link of my previous comment. – ryyker Sep 15 '21 at 12:56
  • 1
    @ryyker: Stack Overflow is no more exclusively a site for debugging prior attempts at coding than software engineering is properly practiced by debugging empty sheets of paper. For many problems, the best approach is not trying something bad and then fixing it and asking for help but rather seeking new knowledge, insights, or ways of viewing a problem. While problem posers on Stack Overflow are expected to attempt to solve their problem first, that attempt does not have to be in the form of writing non-working code. – Eric Postpischil Sep 15 '21 at 12:57
  • I don't understand your output at all. No matter what the value of `r` is, you're showing 3 output values, so it seems you're always computing n choose 3. – William Pursell Sep 15 '21 at 13:04
  • 1
    @EricPostpischil - _"that attempt does not have to be in the form of writing non-working code."_ No, but the work and research should have at least shown an effort at producing the code in the form of a function. More will have been gained by asking a question that was based on much work in attempting to solve it first, then just presenting one algorithm and asking someone to port it into another. – ryyker Sep 15 '21 at 13:07
  • @ryyker: Nonetheless, your request pushes people in the wrong direction, is off-putting, and is bad guidance for Stack Overflow participants. – Eric Postpischil Sep 15 '21 at 13:15
  • 1
    @ryyker: The comment is not “inert.” It pushes Stack Overflow down toward simplistic coding, discouraging discussion of higher-level concepts. There is an abundance of people who can write simple code and are eager to show it off and get “points” for it. There is less supply of concepts and abstractions. Telling people to “include the function that you've tried” is the wrong direction, toward cheap coding and away from thoughtful abstraction. Your comment about tea is *ad hominem*; I wrote nothing about your motivations or emotions, just comments about the text you wrote and its effects. – Eric Postpischil Sep 15 '21 at 13:52
  • @EricPostpischil - Well enough. I am certainly not opposed to supporting behaviors that will create/maintain an effective SO, and it was not my intent that my comment be detrimental to that. However the comment I offered is very representative of what I see on the site every day. By what standard, policy or guideline do you derive that comments such as these reflect the negative effects that you have cited? Or, are there some emerging paradigms written about that I should read describing optimal site behavior? – ryyker Sep 15 '21 at 14:22
  • @EricPostpischil - ... I am also curious about your thoughts on the freely given, but little discussed accepted answer? It appears to be lacking in any discussion of _thoughtful abstraction_. – ryyker Sep 15 '21 at 14:24
  • just FYI, I wrote about such problems e.g. in [these answers](https://stackoverflow.com/search?q=user%3A849891+nested+loops+recursion), in particular, [this answer](https://stackoverflow.com/a/61216006/849891) contains also some links, incl. to some C++ Q&As. see if any of it helps. – Will Ness Sep 18 '21 at 15:02

1 Answers1

3

Indeed we can use recursion to build the n-levels deep structure of the nested for loops, performing the action at the deepest level of recursion.

Or, equivalently, we can build n-1 levels and perform the last for loop explicitly, like this:

#include <stdio.h>

void rec(const char *pre, int n, int lo, int hi) {
    if (n == 0) return;
    if (n > 1) {
        for (int k = lo; k <= hi; k++) {
            char tmp[100]; // 100 is enough for home use
            sprintf(tmp, "%s %d", pre, k);
            rec(tmp, n - 1, k + 1, hi);
        }
    } else {
        for (int k = lo; k <= hi; k++) printf("%s %d\n", pre, k);
    }
}

int main(void) {
    rec("", 3, 0, 5); // use 3 values from 0 to 5
    return 0;
}

This creates sorted triplets of numbers in the 0..5 range. Output

 0 1 2
 0 1 3
 0 1 4
 0 1 5
 0 2 3
 0 2 4
 0 2 5
 0 3 4
 0 3 5
 0 4 5
 1 2 3
 1 2 4
 1 2 5
 1 3 4
 1 3 5
 1 4 5
 2 3 4
 2 3 5
 2 4 5
 3 4 5

Replacing the call in main with rec("", 4, 0, 5); creates 4-tuples; the output is

 0 1 2 3
 0 1 2 4
 0 1 2 5
 0 1 3 4
 0 1 3 5
 0 1 4 5
 0 2 3 4
 0 2 3 5
 0 2 4 5
 0 3 4 5
 1 2 3 4
 1 2 3 5
 1 2 4 5
 1 3 4 5
 2 3 4 5

Added my thought process to write the recursive function

I know a recursivity solution is based on "reduce complexity and recurse". So I want to "solve" n loops when I know how to do n-1 loops.
But I don't know how t do n - 1 loops!

Wait... I know how to 0 loops. It's easy (but not helpful): just do nothing

if (n == 0) return;

I also know how to do 1 loop. Just print the numbers

if (n == 1) for (int k = lo; k <= hi; k++) printf("%d ", k);

This is good. Can be used to do n loops.

How to do n loops?
For each available number, save the number and recurse with 1 less loop and adjusted limits.

It was this that generated that code. After writing the code I could have studied it attentively and stream line some aspects, but decided to post as it was.

pmg
  • 106,608
  • 13
  • 126
  • 198
  • What problem did turning this recursive solve? The disassembly looks quite horrible and I would assume this code is much slower than what the OP already had. – Lundin Sep 15 '21 at 14:14
  • 1
    Although this (nearly) code-only answer seems to solve the current problem, it might not help the OP or other users in learning how to derive such a solution from the original code. Some explanation might be helpful. – Bodo Sep 15 '21 at 14:22
  • You can "hide" several `for` loops in one argument. – pmg Sep 15 '21 at 14:22
  • 2
    @Lundin The code in the question uses exactly 3 loops to choose 3 elements. The code in the answer allows any number of loops/elements as long as the buffer `tmp` is large enough to hold the output. – Bodo Sep 15 '21 at 14:26
  • Generally you don't want infinite size let alone infinite recursion, so I don't see how that's a benefit. Even if it was, I wouldn't throw all that is performance and good programming practice out the window. – Lundin Sep 15 '21 at 14:29
  • @Lundin - _Generally_ is not always part of the requirement. Sometimes a simple _one off_ is wanted. The OP has asked for recursion. This answer addressed that request. Its already known that recursion is [rarely the most efficient way to code anything in C](https://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping). But efficiency was not part of the stated goal here. – ryyker Sep 15 '21 at 14:33
  • @ryyker how would you code an _arbitrary_ number of nested loops if not with recursion? what about recursive backtracking? these seem to _require_ the use of recursion, C or no C. why not enumerate a balanced tree recursively if the depth is guaranteed to be logarithmic? these cases might fall under the qualification of "rarely", sure. :) – Will Ness Sep 16 '21 at 07:40
  • @pmg started editing before seeing your edit. :) – Will Ness Sep 16 '21 at 08:01
  • BTW you don't *have* to special case the `n=1`, and can just do `printf("%s\n", pre)` at `n=0`, removing the code duplication. (this will probably harm efficiency). – Will Ness Sep 16 '21 at 10:56
  • Right @WillNess, that's part of the "stream lining" process :-) – pmg Sep 16 '21 at 11:44
  • 1
    @WillNess - Read my comment in the context of what Lundin was suggesting. I was attempting to counter his complaints as having nothing to do with OP request, and that this answer indeed does a good job of addressing the question. (i.e. Lundin argues that this recursive version is throwing away all of the efficiency of the loops. But question is specifically _how to do it recursively_, efficiency be damned :) ) – ryyker Sep 16 '21 at 11:44
  • @ryyker uh, right, you're completely correct about that. :) – Will Ness Sep 16 '21 at 17:46
  • @pmg see if [this](https://stackoverflow.com/questions/69193274/how-to-change-nested-for-loops-to-recursive-function-for-arbitrary-number-of-loo#comment122371623_69193274) interests you at all. – Will Ness Sep 18 '21 at 15:06