Recursion problem in C

Question

Hi there. I've been trying to solve this problem for a few days now but it seems I haven't grasped the concept of recursion,yet.

I have to build a program in C (recursion is a must here but loops are allowed as well) which does the following: The user inputs 2 different strings.For example: String 1 - ABC String 2 - DE

The program is supposed to print strings which are combined of the ones the user has entered. the rule is that the inner order of the letters in each string (1&2) must remain. That's the output for string1=ABC & string2=DE ":

abcde abdce abdec adbce adbec adebc dabce dabec daebc deabc

If anyone could give me a hand here, it would be great. Thanks guys.

Answer 1

I don't feel like I want to write down the whole algorithm. However, here are some leads that might help you.

Basically, you must merge two strings, keeping the characters order. It's like you have 2 stacks of possibly different sizes.

In your example:

stack #1: A B C
stack #2: D E

You also know that the resulting string will have as length the sum of the length of the two input strings. (So you know already how much length to allocate)

If you proceed character by character: each turn you can choose wether to pop one character from either the stack #1 or the stack #2, then continue. (Here could be the recursion). If you roll up all the possible calls you'll have all the resulting strings.

I use to like problems like that when I was in college: it can seem difficult sometimes, but it is so rewarding when you solve it by yourself !

Feel free to comment if you need more clues.

Answer 2

Here is a partial solution in Java: it should be instructive:

public class Join {                                       // prints:
   static void join(String s, String s1, String s2) {     // ABCde
      if (s1.isEmpty() || s2.isEmpty()) {                 // ABdCe
         System.out.println(s + s1 + s2);                 // ABdeC
      } else {                                            // AdBCe
         join(s + s1.charAt(0), s1.substring(1), s2);     // AdBeC
         join(s + s2.charAt(0), s1, s2.substring(1));     // AdeBC
      }                                                   // dABCe
   }                                                      // dABeC
   public static void main(String[] args) {               // dAeBC
      join("", "ABC", "de");                              // deABC
   }
}

How it works

Basically you have String s, the "output stream", and String s1, s2, the "input stream". At every opportunity, you first take from s1, and later you try again and take from s2, exploring both options recursively.

If at any time either "input stream" is empty, then you're left with no other choice but take whatever's left (if any).

Answer 3

Here it is in C, based on the same idea @polygenelubricants used. It's not that I stole his idea, it's that this is a classical problem and this is the simplest approach :).

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

void solve(const char *str1, const char *str2,
           const int length1, const int length2,
           char *output, int pozOut, int pozIn1, int pozIn2)
{
    if (pozIn1 == length1 && pozIn2 == length2)
    {
        printf("%s\n", output);
        return;
    }

    if (pozIn1 < length1)
    {
        output[pozOut] = str1[pozIn1];
        solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1 + 1, pozIn2);
    }

    if (pozIn2 < length2)
    {
        output[pozOut] = str2[pozIn2];
        solve(str1, str2, length1, length2, output, pozOut + 1, pozIn1, pozIn2 + 1);
    }
}

int main()
{
    char temp[100]; // big enough to hold a solution.
    solve("ABC", "12", strlen("ABC"), strlen("12"), temp, 0, 0, 0);

    return 0;
}

This can be improved. For example, how would you get rid of some of the parameters?
Also, this has a bug: you should make sure that output contains a '\0' at the end before printing it, otherwise you might get unexpected results. I'll leave that for you to fix.

Answer 4

The same algorithm as IVlad, but dynamically allocating the result array, and using pointers rather than indexes making it a bit clearer I think.

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

void solve(const char* result, const char* x0, const char* x1, char* p) {
    if (!*x0 && !*x1) printf("%s\n", result);
    if (*x0) {
        *p = *x0;
        solve(result, x0 + 1, x1, p + 1);
    } 
    if (*x1) {
        *p = *x1;
        solve(result, x0, x1 + 1, p + 1);
    }
}

int main(int argc, char* argv[]) {
    if (argc >= 3) {
        size_t total_length = strlen(argv[1]) + strlen(argv[2]) + 1;
        char *result = malloc(total_length);
        if (result) {
            result[total_length - 1] = '\0';
            solve(result, argv[1], argv[2], result);
            free(result);
        }
    }
    return 0;
}