CODEWITHSUNDEEP
crecursionpermutation
Suzanne
Suzanne

Reputation: 46

For loop creates error when recursivley permutating strings in C

I am new to C and am trying to write a function that returns the all the permutations of a subset of size k of a string using recursion. For example, for the string 'abc' and k = 1, I would get 'a', 'b' and 'c', for k = 2 I would get 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb' and 'cc', and so on.

I want to return all the generated strings so that I can do other things with them - right now it just prints them out, but I will use them later. I wrote this code:

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

#define CHARS "abc"

char *recur(char* prefix, int k, int n);

int main(void)
{     
    int k = 2; //for example
    int n = strlen(CHARS); //set n as length of CHARS
    //print string generated by recur
    printf("string: %s\n", recur("", k, n));
}

char *recur(char *prefix, int k, int n)
{
    //if base case (have already added all letters), return string
    if (k == 0)
    {
        return prefix;
    }
    //otherwise, add character from CHARS to string
    else
    {
        for (int i = 0; i < n; i++)
        {
            // for each letter in CHARS, make a new prefix and add a letter from chars to it
            int prefLen = strlen(prefix);
            char newPrefix[prefLen + 2];
            strcpy(newPrefix, prefix);
            newPrefix[prefLen] = CHARS[i];
            newPrefix[prefLen + 1] = '\0';
            return recur(newPrefix, k-1, n);
        }
    }
}

However, I get the error 'recur1.c:40:1: error: control may reach end of non-void function [-Werror,-Wreturn-type]' when trying to compile.

To explore this a bit further, I removed the for loop which results in a reversed string:

char *recur(char *prefix, int k, int n)
{
    //if base case (have already added all letters), return string
    if (k == 0)
    {
        return prefix;
    }
    //otherwise, add character from CHARS to string
    else
    {
        //make a new array called newPrefix, copy current prefix into it and add new letter from CHARS
        int prefLen = strlen(prefix);
        char newPrefix[prefLen + 2];
        strcpy(newPrefix, prefix);
        newPrefix[prefLen] = CHARS[k-1];
        newPrefix[prefLen + 1] = '\0';
        return recur(newPrefix, k-1, n);
    }
}

After substitution of this second function, the code compiles without any issues. Any ideas as to why the version with a for loop won't compile?

Upvotes: 0

Views: 60

Answers (2)

Bathsheba
Bathsheba

Reputation: 234665

If i < n is 0 when for (int i = 0; i < n; i++) is encountered then program control does not enter the for loop body, and a return statement is not reached. Should the return statement really be in the for loop body?

If that happens, the behaviour of the whole program is undefined. Your compiler is warning you of that, and you have elevated warnings to fail program compilation.

Worse than that, newPrefix has automatic storage duration. You are returning a pointer to it, and that pointer is invalid in the function caller. That's more undefined behaviour.

Upvotes: 0

Sander De Dycker
Sander De Dycker

Reputation: 16243

If n <= 0, then the for loop will never be entered, and so the return statement in the loop body will never be reached. Since there's no return statement after the loop, the compiler complains (rightly so).

That said : are you sure it's not a mistake to have an unconditional return statement inside the loop body ? That makes the loop quite useless.

Upvotes: 1

Related Questions